## To infinity...

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.

There it is: sum up all even fibonacci numbers below 4 million. I already know how to sum and checking the value and even-ness of the number is easy. The only thing left to do is create a function for generating fibonacci numbers. Haskell doesn't have a built-in fibonacci number generator but there is one in the tutorials.

`fibs = 1 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ] `

There is that fibs function that returns a list of fibonacci numbers. The first two elements of the list has the value of 1 followed by a list comprehension zips the current fibs it's tail and then adds the values of each item. This function creates an infinite list of fibonacci numbers so when I run it in winhugs, I get this:

`Main> fibs`

`[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987{Interrupted!} `

I edited the output to remove the pages and pages of fibonacci numbers that got generated in the two seconds that the function was running before I was able to press Ctrl-C. Looking at the output, I know that it's generating the correct values. But I don't need the whole infinite list of fibonacci numbers: I only need the first ones that are under 4 million.

In Haskell, you can get the first few items of the list by using the `take`

function:

`Main> take 20 fibs`

[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]

Good, I got the first two fibonacci numbers. Now, I should probably get more and then visually check how many do I need before I hit the first number that is above 4 million.

`Main> take 30 fibs`

[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]

Main> take 40 fibs

[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040, 1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,

63245986,102334155]

Main> take 35 fibs

[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040, 1346269,2178309,3524578,5702887,9227465]

Main> take 33 fibs

[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, 10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,

1346269,2178309,3524578]

There you go. I got the first 40 and then noticed that the last item is now on the hundred million, did some manual binary search of `take 35 fibs`

and then `take 33 fibs`

until I found that last item is under 4 million.

Next step is take just the even numbers. There is this `filter`

method meant just for that:

`Main> filter (even) [1..10]`

[2,4,6,8,10]

Looks good. Now I only have to plugin the take 33 fibs in there and I have a list of all the fibs under 4 million, and then sum it up.

`sum (filter (even) (take 33 fibs)) `

Good.Project Euler accepted my answer.

Am I done? Well, I don't really like the hardcoded take 33 in the code. I want the code decide when to stop taking numbers out of `fibs`

. Good thing `take`

has this brother `takeWhile`

that does the same thing butis more helpful. The `takeWhile`

function expects two parameters: a predicate and a list. I can use `takeWhile`

and then pass in a lambda that returs true as long as the current number is under 4 million. Let me test that:

`Main> takeWhile (\x -> x < 5) [1..10]`

[1,2,3,4]

Cool. I can now use `takeWhile lambda`

instead of the hardcoded `take 33`

and it should still give me the correct result:

`sum (filter (even) (takeWhile (\x -> x < 4000000) fibs)) `

I also read somewhere (I can't find the link) that you can sequence nested function calls like this using the $ function/operator. Let me try that:

`sum $ filter (even) $ (takeWhile (\x -> x < 4000000) fibs) `

It worked. That's it. Here's the complete source.

`fibs = 1 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ]`

euler2 = sum $ filter (even) $ takeWhile (\x -> x < 4000000) fibs

Done.