[Discuss] What's your favourite Fibonacci implementation and in which language? Mine is in Haskell

PatrickBuhagiar — Fri, 30 Aug 2019 00:27:57 +0000

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 does. 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 zipWith arrays x and y.

In Haskell, the : syntax allows you to concatenate elements or arrays into a single array.

fibs and 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 zipWith on 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 zipWith.

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.

DEV Community: PatrickBuhagiar

[Discuss] What's your favourite Fibonacci implementation and in which language? Mine is in Haskell

Don't know Haskell? I'll explain.