素数的懒惰列表

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]

显然,这不是 Eratosthenes的筛子(感谢Landei).我认为这仍然是一个有益的例子,表明你可以在Haskell中编写非常优雅的短代码,并且可以显示错误数据结构的选择如何严重损害效率.

Answer 2

我建议采取本文的其中一个实现:http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 3

在haskell 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

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 的平方的候选项直接添加到素数中，然后筛选其余的以消除所有能被 5 整除的数字。5 * 35 * 4