Понимание понимания списка в Haskell

Question

Это спойлер для задачи №3 Project Euler! Не продолжайте читать, если вы хотите решить это самостоятельно.

Я пытаюсь изучить Haskell, написав программы для Project Euler. На данный момент я пытаюсь решить задачу №3, которая запрашивает наибольший простой коэффициент числа 600851475143.

Для этого я создаю список liste, который содержит все числа, которые являются делителями этого числа (вверх к его squareroot). Теперь моя стратегия состоит в том, чтобы подсчитать делители этих чисел, чтобы решить, являются ли они главными.

number = 600851475143 
-- sn = sqrt number 
sn = 775146 

liste = [x | x <- [1..sn], (mod number x == 0)] 
-- liste = [1,71,839,1471,6857,59569,104441,486847] 

primelist :: Int -> [Int] 
primelist z = [y | y <- [1..z], mod z y == 0] 

main = print [primelist x | x <- liste] 

Результат, который должен появиться здесь, должен быть список, содержащий 8 списков с делителей элементов liste. Вместо этого список

[[1],[1,3],[1,29],[1,3,29,87]] 

печатается.

Как объяснить это поведение?

Answer 1

Проблема заключается в заявлении типа primelist :: Int -> [Int]. Это заставляет Haskell использовать собственные целые числа, т. Е. 32-битные целые числа на 32-битной платформе. Однако, если вы оставите это, Haskell выведет тип функции в Integer -> [Integer]. Целые числа позволяют вычислять с произвольной точностью, но немного медленнее, чем родные.

Цитирую из "What's the difference between Integer and Int" в Haskell FAQ:

Операции на Int может быть гораздо быстрее, чем операции на Integer, но переполнения и опустошения может вызвать Weird ошибки

. Теперь не правда.

Answer 2

Я не уверен, поможет ли это вам, но я также работаю через Project Euler, чтобы помочь преподавать m yself Haskell, и я придумал следующее решение:

defacto :: Integer -> Integer -> Integer 
defacto x p | x == p = 1 
      | x`mod`p==0 = defacto (x`div`p) p 
      | otherwise = x 

gpf :: Integer -> Integer 
gpf = \x -> prim (x,primes) 

prim :: (Integer,[Integer]) -> Integer 
prim (x,(p:ps)) | p > x = 1 
       | (defacto x p) == 1 = p 
       | otherwise = prim((defacto x p),ps) 

n :: Integer 
n = 600851475143 

Здесь defacto де-факторы штриха из числа, так defacto 2 12 возвращает 4 и defacto 5 14 возвращает 14. gpf является функцией, чтобы найти наибольший простой множитель, хотя для этого требуется список простых чисел до x. Ключевым компонентом является prim, который либо возвращает 1, если число меньше, чем следующее простое число, возвращает первое простое в его премьер-листе, если х - совершенная степень этого простого (т. Е. Если все остальные простые числа, меньшие, чем p, от x) и в противном случае выполняет рекурсивный вызов дефакторизованного x и усеченного первичного списка. Это приводит к непрерывному сокращению x при линейном перемещении основного списка, поэтому нам не нужно проверять какие-либо простые числа, которые не могут влиять на x, и нам не нужно продолжать повторять те же простые числа при уменьшенном значении x. Надеюсь, это вам поможет.