PatrickBuhagiar

Posted on Aug 30, 2019

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

#discuss #functional #todayilearned #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.

Top comments (5)

PatrickBuhagiar • Aug 30 '19 • 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 • Sep 2 '19

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 • Sep 2 '19 • 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 • Aug 30 '19 • 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 • Aug 30 '19

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

DEV Community

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

Don't know Haskell? I'll explain.

Top comments (5)

Read next

Secure API Development: Best Practices with Laravel

Open Source Under Fire: Analyzing the WordPress vs. WP Engine Controversy

Ubuntu's Code Name Philosophy

What 10,000 Hours of Coding Taught Me: Don't Ship Fast