euler !! 1

As promised, today we'll be moving on to Euler problem 2. To solve it, we'll have to write an implementation of the Fibonacci sequence. The full problem description follows.


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

One of the cool things about Haskell is that it is lazily evaluated. This means that it won't try to calculate a value until you specifically ask for it. One neat benefit of this is that it allows us to construct infinite ranges, since the list isn't stored in memory until we reference it! This is useful for Euler problems, since they often involve infinite sequences.
There are multiple ways to construct the Fibonacci sequence in Haskell, so let's examine a few. We know that a Fibonacci number can be found by summing the previous two numbers, and we know that the first two numbers are 0 and 1. So we can easily define a function using these facts:

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

It's neat that we can define "special cases" for our functions in this way. In Perl (and most imperative languages), we would have to write a statement like, "if the input is x, then return y." I prefer the Haskell approach because it gives these special cases a sort of mathematical gravitas; we define the first Fibonacci number to be 0.
Anyway, we can use this function to construct an infinite sequence using map:

fibs = map fib [1..]

map does what you would expect: it maps a function onto a set of values. Also note that we define infinite ranges by omitting their upper bound.
Of course, it would be nice if we could skip the function definition and just construct the sequence from scratch. One way to do this is with the scanl function. scanl takes a function, an initial value, and a list as arguments. It first applies the function to the initial value and the first value of the list. This result then replaces the initial value, and the process repeats. Each result is placed into a new list, which is the return value (note that the first element of this list will always be the initial value). This function is perfect for constructing the Fibonacci sequence; it's almost like they were made for each other! Here's the implementation:

fibs = 0 : scanl (+) 1 fibs

Here we use the : operator to tack on a 0 at the start of the list. Thus, to calculate fibs!!2 (this is how lists are accessed, by the way -- hence the title), we scanl over the initial list (which just contains 0) to get [1,1] and add 0 to the beginning to get [0,1,1]. To calculate fibs!!3, we scanl over the list [0,1,1] and append to get [0,1,1,2,3].
Another way of generating the Fibonacci series is to use zipWith, which "zips" two functions together with some specified function. I won't get into the specifics, but you can see for yourself how it works:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
-- Example:
--     [0,1,1,2,3,5]   (the original sequence)
--   + [1,1,2,3,5]     (this is the "tail")
--   = [1,2,3,5,8]     (result of zipWith)
--     [0,1,1,2,3,5,8] (append 0 and 1 to get the new sequence)

Why are we generating this sequence again? Right, to solve the Euler problem. Now that we have the sequence, we can write a simple list comprehension to perform the necessary computation. Our criteria in this case are that the values of x must even and less than 4 million. As before, we can easily sum the result of the list comprehension to get our answer:

problem2 = sum [ x | x <- takeWhile (<= 4000000) fibs, even x]

Note that we use takeWhile instead of x <= 4000000; we can't simply draw our values from fibs, since it is infinite, and a list comprehension must (by definition) evaluate every element of the list.
Phew! That was rather exhausting. It makes sense that we have to work hard to understand Haskell code, since it is radically different from "normal" (imperative) languages. The upside is that it can be much more concise and elegant!

Leave a Reply

Theme: Esquire by Matthew Buchanan.