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?
Don't know Haskell? I'll explain.
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.
Top comments (5)
While discussing what I've written here with a colleague, I've come across another neat implementation using
unfoldrfrom this article which I've missed.
unfoldris a method that builds an array list (towards the right) when given an initial seed (in this case, 0 and 1).
Justis a term used in Haskell's
Maybetype, which draws parallel to how
Optionalswork in Java. Think of it as
zipWithimplementation is a canonical example of a performant solution that makes good use of haskell's laziness and terseness. That said, there are a couple of fun variations that I think are nice to look at.
First: I think it's always fun to point out that there's a closed-form solution:
This is only accurate up to around the 25th Fibonacci number because of floating point errors, but it can be fun to use when conversations about how to calculate it come up.
Second: I think it's fun to point out that
Applicativeinstance that you can use:
or in a slightly less terse style
I'm not sure either of these is a "best" or "favorite" solution, since that's going to be highly dependent on what your specific need is, but I think each of them provides some enlightening information.
Thanks for sharing Rebecca, I've actually learnt something new today about how to use
It's very neat, I like it!
That is a nice fibonacci! I love Haskell because no matter how nicely I think I've seen a solution expressed there's always something neat I hadn't quite seen. In a similar vein, I like the example from the Clojure docs for lazy-seq:
You don't really need to know Clojure much at all to read this and understand what it does.
I've yet to dabble in Clojure, but thanks for sharing!😁 You're right, it certainly is easier to understand without knowing the language