Programming

This is the second tutorial on solving Project Euler problems using Haskell. Hope you will enjoy!

Problem Description:

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.

Again, create a new text file and call it euler2.hs

First, we are required to make a function that computes the numbers of the Fibonnacci sequence. From the definition fib(x) = fib(x-1) + fib(x-2), we can easily code this in Haskell.

Here is how it would look:

fib :: Int -> Int
fib 1 = 1
fib 2 = 1
fib x = fib(x-1) + fib(x-2)

Now on to test this function. Open up ghci, load the file, and type in “fib 30″, which asks for the 30th Fibonacci numbers.  Actually, this will be quite slow, here are my results:

*Euler1> fib 30
832040
(2.46 secs, 172153128 bytes)

2.46 seconds to get the 30th number ? Way too slow. What is happening here, is that the computer has to do a lot of counting.

fib(30) = fib(29) + fib(28)

= [fib(28) + fib(27)] + [fib(27) + fib(26) ]

and so on and on, expanding the fib, until the problem is reduced to adding up a whole bunch of 1’s together, as the first two terms are 1’s.

So we need a solution, where we don’t need to recompute fib as many times, so you could call it a form of “caching”.

Here is my proposed solution:

fib :: Int -> Int
fib n = table !! n
 where
   table = 0 : 1 : zipWith (+) table (tail table)

Whoa, what’s happening here ? We are creating a “table” of the Fibonacci numbers, and then simply calling the “!!” (value at index) function to get our desired number.

We define a table as a list, with first element 0, and second element 1, and with the rest of the list being computed recursively using “zipWith (+)”.

“zipWith” is a function that takes another function, such as the plus function (+), and two lists, and it “zips” them together using that operator.

For example, zipWith (+) [1,2,3] [1,1,1] will return the list [2,3,4].

Understanding the above revised fib function is best done by simply expanding the recursive bit. Here it is from my prompt.

*Euler1> zipWith (+) [0,1] [1]
[1]
*Euler1> zipWith (+) [0,1,1] [1,1]
[1,2]
*Euler1> zipWith (+) [0,1,1,2] [1,1,2]
[1,2,3]
*Euler1> zipWith (+) [0,1,1,2,3] [1,1,2,3]
[1,2,3,5]
*Euler1> zipWith (+) [0,1,1,2,3,5] [1,1,2,3,5]
[1,2,3,5,8]

So we are seeing how the second parameter of zipWith is our desired sequence. Since Haskell implement lazy evaluation, it will stop computing the list as soon as it reaches “n”.

This approach is also much faster than the previous one. See for yourself!

*Euler1> fib 30
832040
(0.00 secs, 528596 bytes)

0.00 seconds is quite damn fast, and the solution uses up a lot less memory than the previous one!

Now using our knowledge of list comprehensions from the previous tutorial, and the function described above, we can solve problem 2 on Project Euler.

fib n = table !! n
 where
    table = 0 : 1 : zipWith (+) table (tail table)

euler2 = sum[x | x<- takeWhile (<4000000) (map fib [1..]), even(x)]

Line 5 has a couple new function we aren’t familiar with, such as takeWhile, map, and even.

“even” returns true when its parameter is even, and else it returns false. Hence, “even(x)” is one of our conditions for the list comprehension

Now the main part of this is

x <- takeWhile (<4000000) (map fib [1..])

Let’s look at “map” first. “Map” is a function which takes another function, and a list, and it applies that function to every element of the list.

For example, “map (+1) [1,2,3]” will return the list [2,3,4]. Think of this as a kind of a “foreach” loop you might know from imperative programming languages such as C,C++, Java, etc.

Now the “takeWhile” function. This function takes a predicate p, and a list, and returns a list such that all elements in the list meet the predicate p up to a certain point in the list, when we encounter a member that does not follow the predicate, and hence the list is trimmed.

For example, “takeWhile <5 [1,4,2,6,3]” will return [1,4,2] since the number 6 does not follow the predicate, it is NOT less than 5.

So finally, what we are saying, is : “x comes from infinite list of Fibonacci numbers, but trim this list so that we only have elements less than 4 million”

At the very end, use the predefined “sum” function we know from the previous tutorial, to get the sum of the list.

Here is script executing on my machine, very rapidly thanks to that method of computing fibonacci numbers!

*Euler> euler2
4613732
(0.00 secs, 524700 bytes)

Thanks for reading! This is only my second tutorial, so could you please post some comments about improving my style, explanations, etc.

Please come back for more tutorials!