为什么这个主要测试这么慢？

这段代码取自《Haskell Road to Logic, Math andProgramming》一书。它实现了埃拉托斯特尼筛法并解决了欧拉计划问题 10。

sieve :: [Integer] -> [Integer]
sieve (0 : xs) = sieve xs
sieve (n : xs) = n : sieve (mark xs 1 n)
  where
    mark :: [Integer] -> Integer -> Integer -> [Integer]
    mark (y:ys) k m | k == m = 0 : (mark ys 1 m)
                    | otherwise = y : (mark ys (k+1) m)

primes :: [Integer]
primes = sieve [2..]

-- Project Euler #10
main = print $ sum $ takeWhile (< 2000000) primes

实际上它的运行速度甚至比朴素的素数测试还要慢。 有人可以解释这种行为吗？

我怀疑这与迭代标记函数中列表中的每个元素有关。

Thanks.

您正在使用此算法构建二次数量的未评估重击。该算法严重依赖惰性，这也是它无法扩展的原因。

让我们来看看它是如何工作的，希望这能让问题变得显而易见。为了简单起见，假设我们想要print的元素primes无穷无尽，即我们想要一个接一个地评估列表中的每个单元格。primes定义为：

primes :: [Integer]
primes = sieve [2..]

由于 2 不为 0，因此第二个定义sieve适用，并且 2 被添加到素数列表中，列表的其余部分是一个未评估的重击（我使用tail而不是模式匹配n : xs in sieve for xs, so tail实际上并没有被调用，并且不会在下面的代码中添加任何开销；mark实际上是唯一的 thunked 函数）：

primes = 2 : sieve (mark (tail [2..]) 1 2)

现在我们想要第二个primes元素。因此，我们浏览一下代码（供读者练习）并最终得到：

primes = 2 : 3 : sieve (mark (tail (mark (tail [2..]) 1 2)) 1 3)

再次相同的过程，我们要评估下一个素数......

primes = 2 : 3 : 5 : sieve (mark (tail (tail (mark (tail (mark (tail [2..]) 1 2)) 1 3))) 1 5)

这开始看起来像 LISP，但我离题了……开始看到问题了吗？对于中的每个元素primes列表，一个越来越大的堆栈mark必须对应用程序进行评估。换句话说，对于列表中的每个元素，必须通过评估每个元素来检查该元素是否被任何前面的素数标记。mark堆栈中的应用程序。因此对于n~=2000000，Haskell 运行时必须调用函数，从而产生深度约为 ... 我不知道，137900 （let n = 2e6 in n / log n给出下限）？类似的事情。这可能是导致速度变慢的原因；或许vacuum可以告诉你更多（我现在没有一台同时带有 Haskell 和 GUI 的计算机）。

埃拉托斯特尼筛法在 C 等语言中起作用的原因是：

1. 您没有使用无限列表。
2. 由于 (1)，您可以在继续下一个之前标记整个数组n，根本没有调用堆栈开销。