Project Euler Problem 2

Due to my upcoming redundancy, I thought it is about time I learned  some new skills, so naturally I have chosen to learn a language with virtually zero commercial application - Haskell.

If you don't know what Haskell is, it's a functional programming language, which means that is it it deals with what to do, rather than how to do it, as most people are used to with typical procedural languages such as C.

Anyway, a good way to learn a new language is to try it out on some classic problems, such as those on the Project Euler page.

Problem 2 states:

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

The fibonacci sequence starts with 0, 1.. then subsequent entries are constructed by summing the previous two entries. This conveniently recursive definition can be specified in Haskell recursively, ie:

fib :: Int -> Int

fib 0 = 0

fib 1 = 1

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

So the first step in solving this problem is to generate a list of fibonacci numbers... which is very easy to do using Haskell's list comprehension feature:

[ fib x | x <- [0..] ]

This basically says construct a list by calling the function fib x, where x is bound to the range of numbers from 0 to infinity. Infinite lists are a quirky feature of Haskell made possible by its use of lazy evaluation,  which means Haskell will defer actually calculating a result until it absolutely has to. The above expression will keep printing the list until the cows come home, but you will notice that after around 30 elements it gets slower and slower...


This is because it is fiendishly inefficient, having to recalculate each entry in the list from scratch, rather than re-using the previous two entries calculation. Clearly, this approach will not satisfy the Project Euler criteria that the solution should take less than a minute to run.

A new approach to calculate the fibonacci sequence using the results of the previous calculation is shown below:

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

Note that it is recursively defined also. By way of explanation, zipWith is a function which takes two lists and applies a function to the elements in the same corresponding positions in the list and tail is a function which returns a list minus the first element.

So in this case the effect of zipWith is to add the nth element of fibs with the n-1th element of fibs. This function will generate an infinite fibonacci sequence.

We can use a list comprehension to filter out the odd valued terms using the predicate x `mod` 2 == 0.
mod is actually a prefix function (ie: called before its arguments, eg: mod x 2 ), but using `backticks` allows us to call it using infix notation, which is more natural for mathematical functions.

[ x | x <- fibs, x `mod` 2 == 0 ]

Note that the predicate x <= 4000000 will also filter out all values less than 4000000, but the list comprehension will never terminate.

Instead, we can use the takeWhile function which takes values from a list whilst as a boolean criterion is satisfied, eg:

takeWhile ( <= 4000000 ) [ x | x <- fibs, x `mod` 2 == 0 ]

[0,2,8,34,144,610,2584,10946,46368,196418,832040,3524578]

Now all that is left if to sum the list to get our answer

sum (takeWhile ( <= 4000000 ) [ x | x <- fibs, x `mod` 2 == 0 ])

4613732

Which makes me the 139646th person to solve that problem on the Project Euler page. Only 342 left to solve!