## DEV Community is a community of 623,823 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

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.

## Discussion (5)

PatrickBuhagiar • Edited

While discussing what I've written here with a colleague, I've come across another neat implementation using `unfoldr` from this article which I've missed.

``````fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)
take 10 fibs
``````

`unfoldr` is a method that builds an array list (towards the right) when given an initial seed (in this case, 0 and 1).

`Just` is a term used in Haskell's `Maybe` type, which draws parallel to how `Optionals` work in Java. Think of it as `Optional.of()`

Rebecca Skinner

The `zipWith` implementation 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:

``````closedForm :: Integer -> Integer
closedForm idx =
let
phi :: Double
phi = (1.0 + sqrt 5.0) / 2.0
numerator = phi ** fromIntegral idx
denominator = sqrt 5.0
in floor \$ (numerator / denominator) + (1/2)

fibs = map closedForm [0..]
``````

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 `(->)` has an `Applicative` instance that you can use:

``````fibs = 0 : 1 : (zipWith (+) <*> tail) fibs
``````

or in a slightly less terse style

``````fibs =
let
next = zipWith (+) <*> tail
in
0 : 1 : next fibs
``````

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.

PatrickBuhagiar • Edited

Thanks for sharing Rebecca, I've actually learnt something new today about how to use `<*>`.

``````fibs = 0 : 1 : (zipWith (+) <*> tail) fibs
``````

It's very neat, I like it!

Ben Lovy • Edited

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:

``````;; A lazy-seq of Fibonacci numbers (fn = fn-1 + fn-2)
;; The producer function takes exactly two parameters
;; (because we need the last 2 elements to produce a new one)
user=> (defn fib
([]
(fib 1 1))
([a b]
(lazy-seq (cons a (fib b (+ a b))))))

user=> (take 5 (fib))
(1 1 2 3 5)
``````

You don't really need to know Clojure much at all to read this and understand what it does.

PatrickBuhagiar

I've yet to dabble in Clojure, but thanks for sharing!π You're right, it certainly is easier to understand without knowing the language