How does Haskell compute this enormous number instantly?

Question

I am beginning to learn Haskell, and one of the things I like to do when I'm learning a new language is to do Project Euler problems as a supplement to my main reference material.

I have come up with the following solution to the second problem of finding the sum of the even Fibonacci numbers less than four million:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
f :: Integer -> Integer
f n =
  let evenFib = filter (\n -> n `mod` 2 == 0) fibs
  in sum (takeWhile (<n) evenFib)

This works great; f 4000000 returns the correct answer. It does so instantly. Curious, I started typing in larger and larger numbers...

Prelude> f 40000000
19544084
Prelude> f 400000000000
478361013020
Prelude> f 40000000000000000000000000000000
13049874051046942401006156573274
Prelude> f 2370498572349582734598273495872349587234958723948752394857
2805750129675962215536656398462489370528480907433875715844

Each of these values is returned immediately. I have no way of guaranteeing the veracity of the last two answers, because my implementations in other languages don't work for numbers this large.

So, my question is, what is Haskell doing here? How is it returning these values instantaneously (whether they're actually correct or not)? Furthermore, are these answers indeed correct, or is Haskell just making stuff up?

Answer 1

It's likely nothing to do with Haskell in particular but the algorithm you're using for the other solutions.

As fibonacci numbers grow quite quickly (they get 1.6x larger on average each step), there's not that many fibonacci numbers less than 40000000000000000000000000000000, probably less than 100.

A computer adding less than 100 numbers of this size (which isn't particularly big) should take microseconds.

I'm not sure what your other implementations look like, but a common mistake is to write the Fibonacci function like this:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

This is terrible, as fib n calls fib (n-1), which then calls fib (n-2), and returns the answer to fib n. But then you have to go an calculate fib (n-2) again because you haven't saved the answer.

A better implementation of fib in Haskell (or indeed any other language) is like the following:

fib 0 = 0
fib n = fib' 0 1 n

fib' _ curr 1 = curr
fib' last curr n = fib' curr (last+curr) (n-1)

Notice that each fib' call only makes one recursive all, not two. What I've written above is roughly what 0 : 1 : zipWith (+) fibs (tail fibs) is doing, but the above code is a bit messier but probably also easier to translate into other languages.

Answer 2

The answers should be correct.

You can :set +s to make ghci print memory/time information.

Running your tests again, you can see that it's actually using more and more memory:

Prelude> :set +s
Prelude> :{
Prelude| fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Prelude| f :: Integer -> Integer
Prelude| f n =
Prelude|   let evenFib = filter (\n -> n `mod` 2 == 0) fibs
Prelude|   in sum (takeWhile (<n) evenFib)
Prelude| :}
(0.14 secs, 0 bytes)
Prelude> f 40000000
19544084
(0.02 secs, 83,440 bytes)
Prelude> f 40000000
19544084
(0.01 secs, 83,200 bytes)
Prelude> f 400000000000
478361013020
(0.01 secs, 94,800 bytes)
Prelude> f 40000000000000000000000000000000
13049874051046942401006156573274
(0.01 secs, 149,400 bytes)
Prelude> f 2370498572349582734598273495872349587234958723948752394857
2805750129675962215536656398462489370528480907433875715844
(0.01 secs, 225,488 bytes)

And to understand why it's so fast, take a look at the start of evenFib

Prelude> sequence_ $ map (putStrLn . show) $ take 20 $ filter ((== 0) . (flip mod 2)) $ fibs
0
2
8
34
144
610
2584
10946
46368
196418
832040
3524578
14930352
63245986
267914296
1134903170
4807526976
20365011074
86267571272
365435296162
(0.02 secs, 203,472 bytes)

The numbers are growing fast, so there really isn't much work to do.