Haskell脚本耗尽空间

Question

我正在使用项目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.

我需要做些什么来解决这个问题？我尝试编写一个使用累加器的尾递归(我认为)版本,但也无法使用它.

Answer 1

首先,你不应该使用拥抱.这是一个仅用于教学目的的玩具.

然而,GHC是一个快速,多核准备的Haskell优化编译器.来吧.特别是,它进行严格性分析,并编译为本机代码.

关于你的代码突出的主要问题是在一个非常大的列表中使用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甚至纤维将使用相当大的空间,因此需要一段时间.

这是第一个400k偶数纤维的总和,为您节省一些时间(21s).:-)

Answer 2

一些观察/提示:

• 在x + sum从连s的没有得到评估,直到最后一刻
• 你正在服用前4,000,000个纤维,而不是最多4,000,000纤维
• 有一种更简单的方法可以做到这一点

编辑以回应评论

我不会告诉你更简单的方法是什么,因为这是Project Euler问题的乐趣.但我会问你一堆问题:

• 连续多少个甚至纤维？
• 你有多长时间没有平衡？
• 如果你总结所有偶数纤维和所有奇数纤维(手工完成),你会注意到什么？