2

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

我需要做什么来解决这个问题？我尝试编写一个使用累加器的尾递归（我认为）版本，但也无法让它工作。

4

5 回答 5

8

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

然而，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 甚至 fibs 将使用相当多的空间，因此需要一段时间。

这是前 400k even fibs 的总和，为您节省一些时间（21s）。:-)

于 2009-04-10T03:44:59.840 回答
6

一些观察/提示：

  • 来自 even的x + sums 直到最后才被评估
  • 你拿的是前 4,000,000 个小谎言，而不是 4,000,000 个之前的小故事
  • 有一种更简单的方法可以做到这一点

编辑以回应评论

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

  • 你可以连续吃多少个小谎言？
  • 没有一个均匀的谎言你能坚持多久？
  • 如果你把所有的偶数和奇数都加起来（用手做），你注意到这些总和是什么？
于 2009-04-10T02:17:22.547 回答
4

你理解错了问题。实际问题是要将所有偶数斐波那契数相加，以使斐波那契数本身不超过 400 万（恰好是前 33 个斐波那契数）。

于 2009-04-10T04:11:18.857 回答
3

您正在评估fibs. 这些数字呈指数增长。我不知道代表第 100 万个斐波那契数需要多少字节；只有千分之一的斐波那契数有 211 个十进制数字，所以这将需要 22 个 32 位字来保存数字，不要介意任何开销gmp。这些呈指数增长。

练习：计算保存四百万斐波那契数所需的内存量。

于 2009-04-10T02:14:42.273 回答
2

查看 Prelude 函数 takeWhile、filter、even 和 sum

takeWhile (<40) [0..]
甚至过滤 $takeWhile (<40) [0..]

把它们放在一起：

ans = sum $ filter even $ takeWhile (< 4* 10^6) fibs

于 2009-04-11T05:19:33.117 回答