Факторизация целого числа рекурсивно и некоторые вопросы о функциях в Haskell - PullRequest
Новая
       91

Факторизация целого числа рекурсивно и некоторые вопросы о функциях в Haskell

1 голос
/ 03 мая 2020

Я только начал изучать Haskell после перехода с Python, и у меня есть пара вопросов о функциях. Я написал следующий код: 

--generating prime list
primes = sieve [2..]
sieve (p:ps) = p : sieve [x | x <- ps, mod x p /= 0]

--factorising function
--takes an input of a number and a list of primes and outputs a list of its prime factors
factorise (n,ps)
    | mod n head ps /= 0    = div n head ps : factorise (div n head ps, ps)
    | otherwise             = factorise (n,tail ps)

Во-первых, когда я пытаюсь скомпилировать, я получаю сообщение об ошибке n, в котором говорится, что я cannot construct the infinite type: a ~ [a] -> a, почему это так?

* 1007 Во-вторых, хотя я понимаю логику c, стоящую за созданием бесконечного списка, почему вы не должны явно указывать типы функции sieve, подразумеваются ли эти типы? Должен ли я, для функции factorise?

Наконец, есть ли более краткий способ написания вышеуказанного алгоритма (который, как я понимаю, ужасно эффективен)?

Ответы [ 2 ]

1 голос
/ 03 мая 2020

Мое решение (я забыл привести базовый вариант для рекурсии, а также некоторые другие исправления): 

--generating prime list
primes :: Integral a => [a]
primes = sieve [2..]

sieve   :: Integral a => [a] -> [a]
sieve (p:ps) = p : sieve [x | x <- ps, mod x p /= 0]

--factorising function
--takes an input of a number and a list of primes and outputs a list of its prime factors
factorise :: Integral a => (a, [a]) -> [a]
factorise (n, ps)
    |   n == 1          = []
    |   mod n f == 0    = f : factorise (v, ps)
    |   otherwise       = factorise (n, tail ps)
    where
        f = head ps
        v = div n f
0 голосов
/ 03 мая 2020

Добавление некоторых скобок здесь и там устраняет проблему: 

factorise (n, ps)
    | mod n (head ps) /= 0  = div n (head ps) : factorise (div n (head ps), ps)
    | otherwise             = factorise (n, tail ps)

Круглые скобки используются для группировки в Haskell. mod n (head ps) является приложением mod к двум аргументам, n и head ps; без запятых mod n head ps - это применение mod к трем аргументам, n, head и ps`, и это просто не проверяет тип.

Действительно, после исправления ошибки все типы успешно выводятся, как 

primes :: Integral a => [a]
sieve   :: Integral a => [a] -> [a]
factorise :: Integral a => (a, [a]) -> [a]

Теперь вы можете специализировать их, если вы так * wi sh, как 

primes :: [Integer]
sieve   :: [Integer] -> [Integer]
factorise :: (a ~ Integer) => (a, [a]) -> [a]

(последний способ написания типа для factorise требуется расширение GADTs).

Для вашего исходного кода с включенной сигнатурой типа 

factorise :: Integral a => (a, [a]) -> [a]
factorise (n,ps)
    | mod n head ps /= 0    = div n head ps : factorise (div n head ps, ps)
    | otherwise             = factorise (n,tail ps)

сообщение об ошибке по сути то же самое. Он говорит «Не удалось вывести (a ~ ([a] -> a))», но все же показывает, что, насколько видит компилятор, тип a также должен быть одновременно [a] -> a (поэтому он также должен быть a ~ [a] -> ([a] -> a), a ~ [[a] -> a] -> ([a] -> ([a] -> a)) , et c. et c. (отсюда и «бесконечная» ссылка на тип в первом сообщении об ошибке)).

Если бы это был действительно тип, который вы намеревались, его можно было бы сделать законным, назвав его и делая его явно рекурсивным, как 

data T a = MkT ([T a] -> T a)

Это допускается . Haskell вполне может иметь рекурсивные типы. В конце концов, простой тип list является рекурсивным, как если бы он был определен как 

data [] a = [] | a : ([] a)
data L a = Nil | Cons a (L a)

. Я оставлю решение проблем эффективности в factorise на потом. С sieve, хотя это довольно просто: его проблема main в том, что он производит только одно простое число за раз, тогда как он вполне способен производить больше, намного больше, чем на каждом шаге.

Можете ли вы найти способ, как?

Ваша factorise функция представляет собой превосходную отрисовку простого алгоритма факторизации деления проб (за исключением нескольких простых ошибок). Один из способов улучшить краткость (и, следовательно, правильность!) - ввести временные переменные с let (или, лучше, where, чтобы иметь возможность использовать их и в охранниках), как в 

factorise (n, ps)
  | mod n f /= 0  =                        -- is the test correct?
                    v : factorise (v, ps)  -- is it really v : ... ?
  | otherwise     = factorise (n, tail ps)
     where
       f = head ps 
       v = div n f

... кроме как никогда! Вы должны включить дополнительный тест, чтобы прекратить составление списка основных факторов.

Можете ли вы найти способ как? :)

...