ProjectEuler Problem 2 - Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

The sequence of fibonacci numbers is defined as follow:

Writing it in Haskell is not that difficult:

fibs = map fib [0..] where fib 0 = 0 fib 1 = 1 fib k = fib (k-1) + fib (k-2)

Getting fibonacci numbers until it exceeds 4 million using takeWhile builtin function:

takeWhile (<4000000) fibs

Greate! It works!! ..Uhh Hmmm... but it takes looong time..

Let's make memoization take part in exploting Haskell's lazy evaluation.

fibs = map fib [0..] where fib 0 = 1 fib 1 = 2 fib k = fibs !! (k-2) + fibs !! (k-1)

Yay!! It also work!! and It's fast like the Flash. What makes it faster is that the new version is not recursively calling fibs function to get already calculated value. fibs is function that returns list of fibonacci numbers and while calculating kth number, (k-1)th and (k-2)th numbers are already ready in the list so it is not necessary to call the function again. Just get that value from list.

Here is another magic:

fibs = 0:1:zipWith (+) fibs (tail fibs)

Pretty cool!!

Now filter only even numbers using bultin filter function:

filter even $ takeWhile (<4000000) fibs

The answer is sum of the list:

sum $ filter even $ takeWhile (<4000000) fibs

in Python