Haskell script running out of space

Question

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.

Answer 1

You are evaluating four million elements of fibs. Those numbers grow exponentially. I don't know how many bytes are required to represent the millionth Fibonacci number; just the one-thousandth Fibonacci number has 211 decimal digits, so that's going to take 22 32-bit words just to hold the digits, never mind whatever overhead gmp imposes. And these grow exponentially.

Exercise: calculuate the amount of memory needed to hold four million Fibonacci numbers.

Answer 2

A number of observations / hints:

• the x + sums from even aren't getting evaluated until the very end
• You're taking the first 4,000,000 fibs, not the fibs up to 4,000,000
• There is an easier way to do this

Edit in response to comment

I'm not going to tell you what the easier way is, since that's the fun of Project Euler problems. But I will ask you a bunch of questions:

• How many even fibs can you have in a row?
• How long can you go without an even fib?
• If you sum up all the even fibs and all the odd fibs (do this by hand), what do you notice about the sums?

Answer 3

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

Answer 4

You understood the problem wrong. The actual problem wants you to sum all the even Fibonacci numbers such that the Fibonacci number itself doesn't exceed 4 million (which happens to be only the first 33 Fibonacci numbers).

Answer 5

have a look at the Prelude functions takeWhile, filter, even, and sum

takeWhile (<40) [0..]
filter even $ takeWhile (<40) [0..]

put 'em together:

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