haskell - 为什么 Haskell 中的递归函数这么慢？

Question

我正在尝试使用 Haskell 模仿 Sieve 来查找小于某个数字的所有素数。我发现其他 Haskell 程序使用 Sieve 方法速度非常快。然而，我编写的以下递归函数非常慢。代码如下

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

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

谁能解释一下为什么这个递归函数这么慢。感谢您的任何帮助，您可以提供。

Answer 1

sieve' 函数的第二个子句进行递归调用 (sieve' n k) 两次，从而使算法在指数时间内执行。

要解决此问题，您可以将该术语绑定(bind)到某个名称，从而确保它被评估一次:

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(公共(public)子表达式消除)的转换并不是一般的优化，而是时间和空间使用之间的权衡，因此最好将决定权留给程序员。

谷歌搜索“CSE”揭示了一些有趣的讨论，其中之一引用this very good example来自 Simon Peyton Jones 1987 年的书《函数式编程语言的实现》(天哪，这本书几乎和我一样老了)