haskell - 在 Haskell 中生成有限的素数列表

Question

Haskell 中有很多关于生成素数的话题，但在我看来，它们都依赖于' isPrime ' 函数，如果我们还不知道素数序列，它应该看起来像:

isPrime k = if k > 1 then null [ x | x <- [2,3..(div k 2) + 1], k `mod` x == 0]
                     else False

( div 可能会替换为 sqrt ，但仍然......)
我试图基于“归纳定义”构造素数(假设我们有一组前 n 个素数，那么第 (n+1) 个素数是最小的整数，这样前 n 个素数中没有一个是它的除数)。我试过用斐波那契数列的方式来做，它是:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fibs !! n
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

我最终得到了这个:

-- checking if second number is a divisor of first one
ifDoesn'tDivide :: Int -> Int -> Bool
ifDoesn'tDivide n k 
    | mod n k == 0 = False
    | otherwise    = True

-- generating list which consists of first n prime numbers
firstPrimes :: Int -> [Int]
-- firstPrimes 1  = [2]
firstPrimes n     = take n primes 
    where primes = 2:(tail primes) ++ 
         [head [x | x <- [3,4..], k <- primes, ifDoesn'tDivide x k == True]]

但是不行，当 n >= 2时栈溢出.关于如何修复它的任何建议？
“Haskell 可以根据自身定义数据结构，从而有效地创建无限数据结构”。前面提到的那些素数和斐波那契数列是根据自身定义数据结构的具体情况，斐波那契数列工作得很好，但这些 primes没有。
我错过了什么，这两种算法在本质上有什么不同吗？
附言所以，我想，我只是在寻找最“Haskellish”的方式来做到这一点。

Answer 1

你总是可以使用 Haskell 中相当优雅的筛子。

primes = sieve [2..]

sieve (p : xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]

所以要得到前 10 个素数

> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

请注意，虽然 isPrime没有明确使用列表推导式确保列表中的每个数字都必须是相对于它前面的所有素数的素数，也就是素数。
这是更有效的，它是 Eratosthenes' sieve 的核心(编辑)。
上面的代码是第一个例子:

梅丽莎 E. 奥尼尔，The Genuine Sieve of Eratosthenes

这篇论文更详细地介绍了 Haskell 中筛法的有效实现以及惰性在计算中的作用。强烈推荐!