Как реализовать список простых чисел в Haskell, чтобы они могли быть получены лениво?
Я новичок в Haskell и хотел бы узнать о практических применениях ленивой функциональности оценки.
Как реализовать список простых чисел в Haskell, чтобы они могли быть получены лениво?
Я новичок в Haskell и хотел бы узнать о практических применениях ленивой функциональности оценки.
Здесь короткая функция Haskell, которая перечисляет простые числа из Грамотные программы:
primes :: [Integer]
primes = sieve (2 : [3, 5..])
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
По-видимому, это не Сито Эратосфена (спасибо, Ландей). Я думаю, что это по-настоящему поучительный пример, который показывает, что вы можете написать очень элегантный, короткий код в Haskell, и это показывает, как выбор неправильной структуры данных может сильно снизить эффективность.
Я бы предложил взять одну из реализаций из этой статьи: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
Существует несколько решений для ленивой генерации простых последовательностей прямо в вики Wiki. Первым и самым простым является Отложенное сито решетки: (старая версия... NB)
primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]
-- or: filter ((/=0).(`rem`p)) t
where (h,~(_:t)) = span (< p*p) xs
Принятый ответ от @nikie не очень эффективен, он становится относительно медленным после нескольких тысяч, но ответ @sleepynate намного лучше. Мне потребовалось некоторое время, чтобы понять это, поэтому вот тот же код, но только с более понятными переменными:
lazyPrimes :: [Integer]
lazyPrimes = 2: 3: calcNextPrimes (tail lazyPrimes) [5, 7 .. ]
where
calcNextPrimes (p:ps) candidates =
let (smallerSquareP, (_:biggerSquareP)) = span (< p * p) candidates in
smallerSquareP ++ calcNextPrimes ps [c | c <- biggerSquareP, rem c p /= 0]
Основная идея заключается в том, что кандидаты на следующие простые числа уже не содержат чисел, которые делятся на любое простое число меньше первого простого числа, данного функции. Так что если вы вызываете
calcNextPrimes (5:ps) [11,13,17..]
список кандидатов не содержит числа, которое делится на 2
или 3
, это означает, что первый непервой кандидат будет 5 * 5
, причина 5* 2
и 5 * 3
и 5 * 4
уже устранены. Это позволяет вам брать всех кандидатов, которые меньше квадрата 5, и добавлять их прямо к простым числам и решать остальные, чтобы исключить все числа, делящиеся на 5.
primes = 2 : [x | x <- [3..], all (\y -> x 'mod' y /= 0)
(takeWhile (<= (floor . sqrt $ fromIntegral x)) primes)]
Первоначально имея 2 в списке, для каждого целого числа x
больше 2, проверьте, все ли primes
y
в primes
таковы, что выполняется y <= sqrt(x)
, x mod y != 0
, что означает, что x
не имеет других факторов, кроме 1 сам.