Fibonacci in Haskell

A quick one today.

There’s a nice implementation of the Fibonacci numbers in Haskell that shows off some of the features of lazy evaluation and infinite lists in Haskell.

Now there are more efficient ways to do this, e.g. the closed-form Binet solution, but this Haskell solution is really rather neat (at least to me). I’ll show the whole thing, then break it down.

fibs :: [Int]
fibs = 1 : 1 : zipWith (+) fibs (drop 1 fibs)

I like this because it clearly shows the way the Fibonacci sequence is defined.

So let’s break it down.

The first line is a type definition, not strictly needed for this example, but it states our intentions: we want to end up with fibs being a list of integers.

The second line is the calculation definition. The top level of the breakdown is splitting the definition into three pieces delimited by the colon :. The : is the “cons operator” which essentially means put the left hand argument at the start of the list defined by the right hand argument. Note that the right hand argument needs to be a list. So ignoring the third argument for now, let’s look at

1 : 1 : []

Reading from right to left, we have an empty list, then we put a 1 at the start of it, getting [1], then we put another 1 at the start of that list getting [1, 1].

That’s the first two elements of the Fibonnaci series.

Then comes the meat of the problem. To make the nth element, we need to add elements n-1 and n-2.

Luckily, Haskell is lazily evaluated, meaning that we only ever calculate something when we need it. It also allows infinite lists. These two features together means that we can define a list in terms of itself (i.e. a recursive definition).

So for now, assume that you have a list of the first five fibonacci numbers: 1, 1, 2, 3, 5.

mylist = [1, 1, 2, 3, 5]

We can “shift” this list one to the left by dropping the first element:

drop 1 mylist
-- [1, 2, 3, 5]

Then we can pair-wise add each element from mylist and this shifted version using zipWith¹.

zipWith (+) my list (drop 1 mylist)
-- [2, 3, 5, 8]

Scehmatically, what’s happening here is:

mylist             [ 1   1   2   3   5   ]
                     +   +   +   +   +
(drop 1 my list)   [ 1   2   3   5       ]

=                  [ 2   3   5   8       ]

See how we’ve generated the next number in the sequence, 8.

Now imagine if the list was infinite:

mylist             [ 1   1   2   3   5   ...]
                     +   +   +   +   +
(drop 1 my list)   [ 1   2   3   5   8   ...]

=                  [ 2   3   5   8   13  ...]

Which is exactly our definition of fibs. Note that the result here drops off the first two 1s, hence we need to add them back in to the result using the cons operator. Hence we have as our solution:

fibs :: [Int]
fibs = 1 : 1 : zipWith (+) fibs (drop 1 fibs)

It’s important to note that this defines the way to calculate the sequence, it doesn’t actually set your CPU off on an unending process of calculating terms. It merely gives us a way to make as many terms as we need, e.g. if we want the first ten numbers, we simply do:

take 10 fibs
-- [1,1,2,3,5,8,13,21,34,55]

Haskell only calculates the ten we need.

I used a similar technique when doing some early Project Euler problems that needed some prime numbers. With a function to test for primality, and the infinite sequence of integers, it’s easy enough to make an infinite list of all the primes like:

primes = filter (primality_test) [1..]

(The filter function takes a predicate function and a list and returns each element of the list for which the predicate is true, [1..] is the infinite list of integers starting a 1)

Whenever I needed, say, the first 100 prime numbers, all I needed to execute was take 10 primes.