Haskell 脚本空间不足

发布于 2024-07-17 01:11:42 字数 516 浏览 6 评论 0原文

我正在使用 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 消耗时不会被释放。

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

原文

I'm using project Euler to teach myself Haskell, and I'm having some trouble reasoning about how my code is being executed by haskell. The second problem has me computing the sum of all even Fibonacci numbers up to 4 million. My script looks like this:

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 gives the error "Garbage collection fails to reclaim sufficient space", which I assume means that the list entries are not released as they are consumed by foldr.

What do I need to do to fix this? I tried writing a tail-recursive (I think) version that used accumulators, but couldn't get that to work either.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

偏闹i 2024-07-24 01:11:42

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

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

这是前 400k 个偶数 fib 的总和，以节省您一些时间（21 秒）。 :-)

Firstly, you shouldn't use hugs. It is a toy for teaching purposes only.

GHC, however, is a fast, multicore-ready optimizing compiler for Haskell. Get it here. In particular, it does strictness analysis, and compiles to native code.

The main thing that stands out about your code is the use of foldr on a very large list. Probably you want a tail recursive loop. Like so:

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))

Besides all this, the first 4M even fibs will use a fair amount of space, so it'll take a while.

Here's the sum of the first 400k even fibs, to save you some time (21s). :-)

回复收藏 0 原文