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.
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.
^ This is the function signature, it says the fib function, is applied to an Integer, and the result is an Integer.
^ 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.
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…
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!
Let’s get the easy bit out of the way:
^ 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.
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:
^ 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.
…
^ 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…
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:
^ this is because we put fib = 1 : ... we haven’t even invoked the scan function at this point.
Taking 2 values from fib:
^ 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.
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?
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.
