Decking the halls with fibonaccis

Today I’d like to show off how awesome the Haskell language is with a few example programs. This blog is valid Literate Haskell, which means that you should be able to copy this entire text, save it with a .lhs extension, and immediatly be able to run the code!

Today I’m going to be showcasing three different ways of computing Fibonacci Numbers.

First some boilerplate code: a module name and some imports. We’ll be using the State Monad for two examples, the function nub from Data.List, and some funky functors in Control.Applicative to help with the testing.

> module Fib where

> import Control.Monad.State
> import Data.List
> import Control.Applicative

The below method comes courtesy of Thomas Hartman from the Patch-Tag blog. I belive that it shows how elegant Haskell code can look, even while using the State Monad to hide the plumbing. This function computes the nth Fibonacci number iteratively, and the below code looks dangerously non-functional. The function takes advantage of the State Monad to store state, but the overall function is still “pure”. Monads give you a lot of expressive power

> fibs1 :: Integer -> Integer
> fibs1 n = flip evalState (0, 1) $ do
>   forM_ [0..n-1] $ \_ -> do
>     (a, b) <- get
>     put (b, a+b)
>     (a, _) <- get
>  return a

The next function computes Fibonacci numbers using a Dynamic Programming method called memoization. Essentially it stores previously computed numbers in a lookup table so that future computations take constant time. Note however that since this code uses a list to store the values, the lookup will not be constant, but it’s simpler this way. For real performance we can use an array or a hash table.

Like the above function, fibs2 uses the State Monad to store some state behind the scenes. This time it stores the table of previously computed values. Every time our function is called, it first checks the table to see if the asked for Fibonacci number has already been computed. If so, no work needs to be done! However if there is no entry for n, fibs2 computes it, stores it, and then returns it! How neat is that! Be careful, the following code isn’t as elegant as the code above:

> fibs2 :: Integer -> Integer
> fibs2 n = evalState (fibs2′ n) [(0,0), (1,1)]
>   where
>     fibs2′ n = do
>        table <- get
>        case lookup n table of
>           Just m -> return m
>           Nothing -> do
>              n’ <- fibs2′ (n-1)
>              n” <- fibs2′ (n-2)
>              let m’ = n’ + n”
>              table’ <- get
>              put ((n, m’) : table’)
>              return m’

Finally we have the naive definition of Fibonacci. This function is almost guaranteed to blow its stack after about thirty iterations. The actual runtime complexity is of order , where is the golden ratio.

> fibs3 :: Integer -> Integer
> fibs3 0 = 0
> fibs3 1 = 1
> fibs3 n = fibs3 (n-1) + fibs3 (n-2)

The final little bit of code simply tests the above three functions to see if they return the same value. We could test this manually, but coding stuff is fun, so why not?

The <*> operator takes a list of functions on the left and applies them to a list of numbers on the right (essentially). We only wish to test our functions on the number n, hence the singleton list. Next the nub function, defined in Data.List, removes duplicate elements from a list. Since all of our functions return the same value (we hope), the resulting list when passed through nub should simply be the nth Fibonacci number. To test this, we check its length. If more than one number remains in the list, that means we have a problem with one of our functions.

Running testFibs, we should get back the value True, meaning all of our Fibonacci functions return the same number back.

> testFibs :: Integer -> Bool
> testFibs n = length results == 1
>     where results = nub $ [fibs1, fibs2, fibs3] <*> [n]

To finish off this post, I’ll also leave you with the famous Haskell one-liner to generate an infinite list of Fibonaccis. The code takes use of a recursive definition and is very concise:

> fibs = 0 : 1 :  zipWith (+) fibs (tail fibs)

If I don’t blog again this season, have a happy holiday, and I’ll see you in the new year