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.