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

我正在试图模拟使用Haskell找到所有素数小于某个数的筛。我发现其他Haskell程序以极快的速度使用Sieve方法。然而，我写的下面的递归函数非常慢。代码如下为什么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

筛20需要约2分钟。在我写这个问题时筛30仍未完成。

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

来源

2011-08-21 user898033

作为Eratosthenes在Haskell中筛选的最终权威，您应该阅读功能规划期刊（2009）中的Melissa O'Neill的文章（http://lambda-the-ultimate.org/node/3127）。应该有更多的技巧。 – ShiDoiSi

您的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年的书引用了所谓的“函数式编程语言的实现”（噢，我的，这本书几乎是一样老，因为我）

来源

2011-08-21 06:08:34 Rotsor

谢谢，这正是问题所在。它现在运行速度更快。 – user898033

我觉得很奇怪，编译器错过了这个优化。 –

@Jon，我已经更新了解决此问题的答案。 – Rotsor

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

回答

相关问题