Euler #2 : Streaming Fibonaccis
by Nicolas Wu
Posted on 8 July 2010
Time for the second problem in our series.
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.
First we’ll show how we can solve this problem using a list comprehension, like in the last post, and then we’ll show a different, far more efficient, solution.
We start by writing a function that, given a value
n, tells us the
nth value in the Fibonacci sequence. The type of this function is as follows:
We begin its definition by describing the two base cases of a Fibonacci number:
For any other value of
n, the definition of
fib is the sum of the two previous values of
The order of definitions matters in Haskell: in this example the case for
n overlaps with the other two cases, and would cause problems if the compiler always matched this case instead of the other two. To resolve these ambiguities, Haskell tries to match lines one after the other before applying them.
Our first goal is to produce a list of consecutive Fibonnaci numbers. This can be obtained by transforming a list of integers by using our function
fib on each element. This kind of transformation is quite common, and a special function,
map, does this for us.
map takes a function and a list as arguments, and applies the function to each element in the list. Here’s its definition:
The definition tells us that when the list is empty, we return an empty list back. Otherwise, we apply the function
f to the first element of the list, and add the result to the front of the list generated by mapping
f to the remainder. Since
map is used all the time, this is a function supplied in the prelude, so we don’t need to define it.
Here’s what we get when we map
fib onto a list of
Using the same technique as in the last question we can produce a first attempt at answering the question:
Here our list comprehension draws the value of
x from the infinite list of Fibonacci values, which is generated using a
map on the list of all natural numbers starting from
2. The predicate we use here tells the list only to accept values smaller than
Unfortunately, this program never terminates: it keeps checking for values even when it has far surpassed the
4000000 mark because it has no notion of the monotonic property that
fib enjoys: the program has no way of knowing that each new value of
x will be greater than the last, and so it keeps checking the next value of
x even after the value of
4000000 has been surpassed, just in case one is found that is smaller.
To get round this problem, we need a function that takes values while they are smaller than
4000000, and when a value greater than this is found, we should stop taking values. This kind of behaviour is captured precisely by a
takeWhile function, which takes values while some predicate holds true, and stops taking values when the predicate is false:
This definition uses slightly different notation than what we’ve been used to because it does a case analysis based on the value of
p x. This case analysis checks each condition to the right of the
| symbol, and uses the definition to its right if the condition evaluates to
True. The first condition passes when
p x holds, and if it does, then the function returns the value of
x added to the front of the result of taking
p holds. If none of the cases pass, then the definition to the right of
otherwise is used, and in this case,
x is discarded, and nothing else is returned. This function is also very common, and found in the prelude.
We modify our answer to make use of this
takeWhile function, and end up with the following definition:
Here we make use of the
(.) operator, known as function composition, which performs one function after another. In this case, we perform a
sum after the result of
takeWhile (< 4000000) applied to our list of even Fibonnacis.
Function composition is very useful since it allows us to chain functions one after the other in a really easy way. Here’s its definition:
The composition of two functions,
g . f, pronounced
f, first applies
f to some value
x, and then applies
g to the result. The type of this operator is a bit confusing at first, but when you consider that the function
f is the first one that is applied to a value of type
a, then everything falls into place.
Although the solution to our problem eventually returns a result, it is incredibly slow and inefficient, taking about 25 seconds before anything is returned on my machine. So we’ll now think of another way of solving the problem.
The reason our previous solution,
euler2', is slow, is that each application of
fib in our
map must be recalculated from scratch. To make our program run faster, we’ll tackle the problem head on by avoiding the use of a
map, and generating the Fibonacci sequence directly, and make use of the fact that each new value in the sequence is related to the previous two.
Here’s a definition that produces an infinite list, sometimes called a stream, of Fibonacci values:
This definition makes use of mutual recursion, where the three functions
fibs'' depend on each other. The interesting case is that of
fibs'', which makes use of a
zipWith function. A
zipWith basically takes a function and two lists, and combines the two lists by using that function to produce another list. Here’s the definition:
The first part of this definition simply applies
y before zipping the rest of the two lists with
f again. The second part of the definition is basically a “catch all” that basically says that if the first pattern doesn’t match, then return an empty list. This uses underscores,
_, instead of values, since underscores match any expression.
Using our new version of
fibs, we get the following solution to the problem:
This version returns its result immediately!
In this post we’ve seen two different solution to our problem, one that uses
map, and another that uses a stream. Here are some of the points we’ve covered:
mapwe can transform one list into another.
takeWhilehelps us limit infinite lists.
- Functions can be composed using the
- Creating streams can be very efficient!
Once again, we’ve covered a lot of ground in this short article, and I hope I haven’t left you confused. I’d love to hear some feedback from you, so please feel free to leave comments!