WARNING! This post contains a spoiler for Problem #2 listed at Project Euler. Do not read the rest of this post if you’re planning to attempt to solve the problem yourself.

Problem #2 in the series is a little step up from the previous question, and involves a little more thought:

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, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Here is my Haskell source that generates the required answer:

-- Infinite list of Fibonacci numbers
fibs :: [Integer]
fibs = 1 : 2 : [ n | n <- zipWith (+) (tail fibs) fibs ]
 
-- function that sums even values of fibs up to a number
sumEvenFibsTo :: Integer -> Integer
sumEvenFibsTo i = sum [ n | n <- takeWhile (<i) fibs, ((mod n 2) == 0)]
 
-- main - the programs entry point when compiled
main :: IO ()
main = print $ sumEvenFibsTo 4000000

As we can see it’s a little more complicated than the previous question, but isn’t too difficult either. I won’t go into the same level of detail as I did before when explaining the solution as I think most of it is obvious. Instead I’ll just explain the bits that are a little convoluted:

1. tail - returns the list with the first item (the head) removed.
2. zipWith - this is a built-in function that is part of Prelude. It takes two lists (the last two parameters) and iterates through each at the same time. For each pair of items (one from each list) it applies the given function.
3. zipWith (+) (tail fibs) fibs - create another list which is made up of the sum of each item in fibs with each item in the tail of fibs.
4. takeWhile - takes from the head of the list until the value meets a given condition.
5. print - displays a value on the screen.
6. $ - this is used as a way of separating function calls. Haskell is aggressive with its argument passing, and hence lots of parenthesis need to be used to make sure it’s obvious what things are associated with each other. the $ operator is just another way of doing the same thing without using parenthesis.

Again it’s a neat solution. Nice and concise. The kicker here is the definition of fibs, the infinite recursive array. In Haskell, you can define a function using references to itself. Lists are just the same, as they’re not evaluated until run-time. So you can define a list with no bounds, and at run-time you have the responsibility of making sure you don’t try and parse the entire structure. This is where the takeWhile function comes in to our solution, we only take values while they’re less than 4,000,000. Because we know that the Fibonacci sequence always increases in size, we know that it will eventually end.

I’ll leave it to you to get your head around the recursive definition. If you want more clarification, just post a comment. Enjoy