Ленивый список простых чисел

Question

Как можно реализовать список простых чисел в Haskell, чтобы их можно было найти лениво?

Я новичок в Haskell и хотел бы узнать о практическом использовании функций отложенной оценки.

Answer 1

Вот короткая функция Haskell, которая перечисляет простые числа из Грамотные программы:

primes :: [Integer]
primes = sieve (2 : [3, 5..])
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

По-видимому, это , а не Сито Эратосфена (спасибо, Ландеи). Я думаю, что это по-прежнему поучительный пример, который показывает, что вы можете написать очень элегантный, короткий код на Haskell, и который показывает, как выбор неправильной структуры данных может сильно снизить эффективность.

Answer 2

Я бы предложил взять одну из реализаций из этой статьи: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 3

Существует множество решений для ленивых генераций простых последовательностей прямо в вики Haskell.Первое и самое простое - это Отложенное сито тернера : ^{(старая редакция ... 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

Answer 4

primes = 2 : [x | x <- [3..], all (\y -> x `mod` y /= 0) 
                   (takeWhile (<= (floor . sqrt $ fromIntegral x)) primes)]

Если изначально в списке 2 для каждого целого числа x больше 2 , проверьте, есть ли все y в primes, так что y <= sqrt(x), x mod y != 0 выполняется, что означает, что x не имеет других факторов, кроме 1 и сам.

Answer 5

Принятый ответ от @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.