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

一些观察/提示：

• 这 x + sumEven 的 s 直到最后才被评估
• 您取的是前 4,000,000 个小谎，而不是 4,000,000 个以内的小谎
• 有一个更简单的方法可以做到这一点

编辑回应评论

我不会告诉您更简单的方法是什么，因为这就是欧拉计划问题的乐趣所在。但我会问你一堆问题：

• 你能连续说出多少个偶数小谎？
• 你能坚持多久而不撒谎？
• 如果您将所有偶数小纤维和所有奇数小纤维相加（手动计算），您会注意到这些总和是什么？

Answer 2

首先，你不应该使用的拥抱。它仅用于教学目的的玩具。

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甚至的FIB 中的总和，以节省你有一段时间（21S）。 ： - ）

Answer 3

您了解的问题是错误的。 要你来总结所有的偶数斐波那契数使得斐波那契的实际问题号本身不超过4000000（这恰好是仅第一33张斐波那契数）。

Answer 4

您正在评估fibs四百万元。这些数字成倍增长。我不知道需要多少字节来表示百万分之一的Fibonacci数;只是千分之一Fibonacci数有211个十进制数字，所以这是要带22个32位字刚刚举行的数字，别提什么开销gmp规定。和这些成倍增长。

动作：calculuate持有4000000张斐波那契数所需要的存储器的量

Answer 5

看看前奏功能takeWhile，过滤器，甚至，和总和

takeWhile（<40）[0 ..]
过滤甚至$ takeWhile（<40）[0 ..]

把“时间一起：

ANS =总和$滤波器甚至$ takeWhile（<4 * 10 ^ 6）的FIB