懶惰的素數列表

Question

如何實現Haskell中的素數列表，以便可以懶惰地檢索它們？

我是Haskell的新手，希望瞭解懶惰評估功能的實際應用。

Answer 1

下面是一個簡短的Haskell功能，從Literate Programs:

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

列舉素數顯然，這是不埃拉託塞尼的篩（感謝，Landei）。我認爲這仍然是一個有啓發意義的例子，表明您可以在Haskell中編寫非常優雅的短代碼，並顯示如何選擇錯誤的數據結構會嚴重影響效率。

Answer 2

有許多解決方案可以在haskell wiki中正確生成素數序列。第一，最簡單的是Postponed Turner sieve：^{（舊版本... 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 3

我建議採取實現一個從本文：http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 4

的接受了@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整除的所有數字。