Haskell脚本空间不足
Haskell脚本空间不足
提问于 2009-04-10 02:01:32
我正在使用项目Euler自学Haskell，我在推理haskell如何执行我的代码时遇到了一些问题。第二个问题让我计算所有偶数斐波那契数的和，直到400万。我的脚本如下所示：
fibs :: [Integer]
fibs = 1 : 2 : [ a+b | (a,b) <- zip fibs (tail fibs)]
evens :: Integer -> Integer -> Integer
evens x sum | (even x) = x + sum
| otherwise = sum
main = do
print (foldr evens 0 (take 4000000 fibs))Hugs给出了错误“垃圾收集无法回收足够的空间”，我认为这意味着列表条目在被foldr消耗时不会被释放。
我需要做些什么来解决这个问题？我试着写了一个使用累加器的尾递归(我想)版本，但也不能正常工作。
回答 5
Stack Overflow用户
回答已采纳
发布于 2009-04-10 02:17:23
以下是一些观察/提示：
x + sum‘s甚至直到最后时刻才会被评估。- 你要进行前4,000,000个谎言，而不是4,000,000
- There是一种更简单的方法来完成此操作
对评论的响应进行编辑
我不会告诉你更简单的方法是什么，因为这就是Project Euler问题的乐趣。但我会问你一堆问题：
- 你能有多少个偶数谎言？
- 你能在没有偶数谎言的情况下坚持多久？
- 如果你把所有的偶数谎言和所有的奇数谎言加起来(用手做)，你会注意到这些和吗？
Stack Overflow用户
发布于 2009-04-10 03:45:00
首先，你不应该使用拥抱。它只是一个用于教学的玩具。
然而，GHC是一个针对Haskell的快速、多核就绪的优化编译器。Get it here。特别是，它进行严格的分析，并编译成本机代码。
你的代码中最突出的一点是在一个非常大的列表中使用foldr。你可能需要一个尾递归循环。如下所示：
import Data.List
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
evens x sum | even x = x + sum
| otherwise = sum
-- sum of even fibs in first 4M fibs
main = print (foldl' evens 0 (take 4000000 fibs))除此之外，前4M的偶数谎言会占用相当大的空间，所以这需要一段时间。
这是the sum of the first 400k even fibs，为了节省你的时间(21秒)。:-)
Stack Overflow用户
发布于 2009-04-10 04:11:19
你对问题的理解是错误的。actual problem希望您对所有偶数斐波纳契数求和，这样斐波纳契数本身就不会超过400万(恰好只有前33个斐波那契数)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/736495
复制相关文章
相似问题
腾讯云开发者
