A few years ago, in my first grad interview, I recall being asked to implement Fibonacci in two different approaches. Back then, I could only think of recursive and iterative approaches in Java. My naïve, young self could not fathom that other approaches could exist.
As the years gone by, I've come across many implementations in different languages and paradigms. This however, has got to be my favourite, in good old Haskell:
When I was first learning Haskell, it took me quite a while to wrap my head around what is going on here. I think it's my favourite implementation because it is a good example of how to use infinite streams and lazy loading.
What's your favourite Fibonacci sequence, in what language, and why?
The key bit to understand here is what
zipWith, which returns an array, incrementally takes an element from two supplied arrays, and performs an operation on them. In this case, I am adding them up with the addition operator. Below is an example of what happens if I
In Haskell, the
: syntax allows you to concatenate elements or arrays into a single array.
fibs' are two functions that I've defined.
fibs returns an array with
1 as its head, and the content of
fibs' as its tail.
fibs' also returns an array that starts with
1, but, as a tail, performs
fibs and itself with the addition operator! Confusing? Here's a step by step breakdown of how the whole thing gets evaluated:
fibs -- we're calling "fibs", which expands to... [1, fibs'] -- but fibs' expands to... [1, 1, (zipWith (+) fibs fibs')] -- recursively we are going keep expanding [1, 1, (zipWith (+) [1, (fibs')] [1, zipWith (+) fibs fibs']) ] -- let's add the first elements in the two arrays supplied for the first zipWith [1, 1, 2, (zipWith (+) [fibs'] [zipWith (+) fibs fibs'])] -- and this will go on for infinity!
Another way to think about what is going on here is that we are essentially having two identical infinite Fibonacci arrays, however one is offset by one index. As a result of this offset,
zipWith would achieve the same effect as adding the two last numbers in the sequence. The initial two ones in the sequence are added before performing
I know what you're thinking. Sure, this would go on to infinity and blow up memory, however Haskell uses lazy loading which means values are only evaluated when needed. The last part of the this implementation is to use
take 10 fibs, which basically returns the first 10 elements of the fibonacci sequence.