Some ways to generate fibonacci in Haskell

The Fibonacci Sequence is a integer number sequence, where each term is the sum of the previous two terms.

I think every programmer has come across this sequence either when they are learning a new language, or because they have to estimate some work in story points.

I thought I would walk through this familiar problem with a few simple-ish Haskell solutions, mainly becuase I think it’s cool, and I think it demonstrates a few really nice features of the language.

1. The classic, co-recursive version.

fib :: Integer -> Integer
fib n 
  | n < 2     = n
  | otherwise = fib (n-1) + fib (n-2)

I think this algorithm explains the sequence really nicely, it reads a bit like the formal definition. I’ll assume you haven’t ever read or written any Haskell and walk you through this, step by step.

fib :: Integer -> Integer

^ This is the function signature, it says the fib function, is applied to an Integer, and the result is an Integer.

fib n 

^ This just tells us that the parameter (the Integer) in the signature, will be assigned to the variable n.

This next bit is a “guard”, and it’s a type of conditional branching.

  | n < 2     = n
  | otherwise = fib (n-1) + fib (n-2)

When n is less than 2, we can just return n. Otherwise, we invoke the fib function with n-1, and once again with n-2, and add them together.

Let’s say we invoke fib with 3: n is greater than 2, so we invoke fib 2 and fib 1 and add the results together.

This is good, but what if we want a list of fibonacci numbers, not just a single fibonacci number for n?

We can map our fib function over a list! For example…

λ> map fib [0..20]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]

This is pretty cool, we’ve learnt a few things about Haskell:

• it has some interesting looking pattern matching
• it supports recursion, like proper recursion, that won’t blow your stack, and is not just restricted to “tail call” recursion.
• you can map functions over data structures, spoiler alert: this turns out to be quite a fundamental concept.

2. Using a scan function

Check out this crazy little one liner!

fib :: [Integer]
fib = 1 : scanl (+) 1 fib

Let’s get the easy bit out of the way:

fib :: [Integer]

^ Tells us the fib function returns a list of Integers.

Onto the meaty bit… Scan functions, are a bit like fold functions - which typically applies function over a data type to yield a single result.

Here we can apply the addition function over a list of the values 1-5, with a starting value of 0.

λ> foldl (+) 0 [1..5]
15

The answer is 15 because: (((((0 + 1) + 2) + 3) + 4) + 5) == 15

A scan function however, is different in that it also returns all of the intermediate values. Let’s swap out the fold for a scan and see the difference:

λ> scanl (+) 0 [1..5]
[0,1,3,6,10,15]

^ The first difference is we get a list result instead of a single value. We can also see that we obtained all of the intermediate values of the computation, all the way up to the final value of 15.

…

fib = 1 :

^ The next bit to understand is that we need to start the list of fibonacci off somewhere, so we say that the list starts with a 1, which is added to the rest of the list (which is calculated by the scan function).

The : character is a cons operator, and is an infix operator used to add a value to a list. Some people say that you cons something to a list. I think the term originated from the language Lisp, which heavily makes use of lists, hence why Lisp programmers are also known as Cons-artists.

…

Finally we have arrived at the fun bit…

fib = 1 : scanl (+) 1 fib

You have to bear in mind is that Haskell is lazily evaluated (or non-strict to be precise). So when we see that the scanl function is mapping the (+) add function over itself, it only needs to compute as much as it needs to determine the answer.

This is probably best explained with a simple example.

If we only take the first value form this sequence, it will be 1:

λ> take 1 fib
[1]

^ this is because we put fib = 1 : ... we haven’t even invoked the scan function at this point.

Taking 2 values from fib:

λ> take 2 fib
[1,1]

^ give us [1,1] and we have invoked the scan function, but we are returning the initial starting value, the '1' in 'scanl (+) 1 fib'.

I think that’s actually the tricky bit explained!

It’s only once we start to get more than one value from fib, that we get to see scan mapping the (+) over the fib function, where it is used.

λ> take 4 fib
[1,1,2,3]

As we already know the first two values passed to the scan function are:
* the initial value 1 which is applied to scanl
* the 1 from the start of the function: 'fib = 1 : ...'.

So when it comes to compute the third fibonacci value, we take the previous two values, and apply the (+) function to them, yielding 2. You can then repeat this pattern for all the remaining infinite fibonacci values.

Here’s a slight variation on this solution, perhaps this one makes more sense to you?

fib :: [Integer]
fib = scanl (+) 1 (1:fib)

Here’s a few more, they’re a bit beyond the scope of the simple explanations though.

fibZip :: Integral a => [a]
fibZip = 0 : 1 : zipWith (+) fibZip (tail fibZip)

fibLC :: [Integer]
fibLC = [a + b | a <- 1:fibLC, b <- 0:1:fibLC]

fibAnamorphism :: Integral a => [a]
fibAnamorphism = unfoldr 
                  (\(a,b) -> let fibNum = a+b in Just (fibNum, (b,fibNum))) 
                  (0,1)

fibAnamorphism' :: Integral a => [a]
fibAnamorphism' = fst <$> iterate (\(a,b) -> (b,a+b)) (0,1)

I hope you enjoyed this little journey into Haskell.