为什么Haskell中的这个递归函数很慢？

Question

我正在试图模拟使用Haskell找到所有素数小于某个数的筛。我发现其他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分钟。在我写这个问题时筛30仍未完成。

任何人都可以解释为什么这个递归函数是如此之慢。感谢您的任何帮助，您可以提供。

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”，揭示了一些有趣的讨论，其中一个由西蒙·佩顿 - 琼斯this very good example从1987年的书引用了所谓的“函数式编程语言的实现”（噢，我的，这本书几乎是一样老，因为我）