为什么这个在Haskell中的递归函数运行如此缓慢？

Question

我试图用Haskell模仿筛法来找出所有小于某个数字的质数。我发现其他使用筛法方法的Haskell程序速度很快。然而，我编写的下面这个递归函数非常慢。代码如下所示：

sieve' :: Integer -> Integer -> [Integer]

sieve' n 1 = [2 .. n]

sieve' n (k + 1) | [x | x <- sieve' n k, x == k + 1] == [] = sieve' n k

    |otherwise = [x | x <- sieve' n k,  x == k + 1 || not (mod x (k + 1) == 0)]



sieve :: Integer -> [Integer]

sieve n = sieve' n n

Sieve 20大约需要2分钟。当我写这个问题时，Sieve 30还没有完成。

有人能解释一下为什么这个递归函数如此缓慢吗？感谢您提供的任何帮助。

- user898033

---

作为Haskell中Eratosthenes筛法的最高权威，您应该查看Melissa O'Neill在Functional Programming杂志（2009年）上的文章（http://lambda-the-ultimate.org/node/3127）。里面应该有更多的技巧。 - Volker Stolz

Answer 1

你的 sieve' 函数的第二个子句会调用递归函数 (sieve' n k) 两次，导致算法的性能呈指数级别下降。

为了解决这个问题，你可以把这个表达式绑定到一个变量上，确保它只被计算一次：

sieve' n (k + 1) | [x | x <- rec, x == k + 1] == [] = rec
    |otherwise = [x | x <- rec,  x == k + 1 || not (mod x (k + 1) == 0)]
  where
    rec = sieve' n k

针对一个评论而进行的更新，解释为什么编译器不会自动执行此操作：

这种转换称为CSE（公共子表达式消除），通常不是优化，而是时间和空间使用之间的权衡，因此最好由程序员决定。

搜索“CSE”可以找到一些有趣的讨论，其中之一引用了Simon Peyton Jones在1987年出版的书《函数式编程语言的实现》中的此非常好的示例。（哦，我的天啊，这本书几乎和我一样老了。）

- Rotsor

---

谢谢，这正是问题所在。现在它运行得更快了。 - user898033

我觉得编译器错过了这个优化很奇怪。 - Jon Purdy