Today I taught my computer architecture class for the last time. My students and I discussed the complexity of the various Fibonacci algorithms. Fibonacci is a function often used to test out new programming languages as it is easy to implement and can showcase many techniques.

Later on I worked with my friend Anders Schmidt who showed me Paul Flavius Nechita's 100 Days UI Challenge. I thought it was cool and wanted to do something similar. But I do not design.

So I decided to program Fibonacci in 100 different programming languages. The idea is to showcase some typical aspects of a programming language and implement the function in the different languages idiomatic ways.

As today is the first day of this project I am going to present Fibonacci in Haskell. This is mostly because I recently have spend quite some time with that language. The formulations of the function is going to be by direct recursion and recursion with accumulation.

Where else would you start? Here we look at Haskell as a practical general purpose language.

In Haskell I did two different implementations. First, the recursive way, which is the way we usually think of problems in a functional context. We use pattern matching to pick out the base and induction cases.

-- Standard recursive implementation, very slowfib :: Integer -> Integerfib 0 = 0fib 1 = 1fib n = fib (n - 1) + fib (n - 2)

However, it turns out that this solution is quite slow due to the exponential fanout with the two recursive calls. Luckily there is another way! So I implemented it using recursion with an accumulator:

-- Using an accumulatorfibAcc :: Integer -> IntegerfibAcc n = doFib n (0,1)    where        doFib :: Integer -> (Integer, Integer) -> Integer        doFib 0 (a, b) = a        doFib n (a, b) = doFib (n-1) (a+b, a)

To keep the type signature identical to the other Fibonacci we uses the where construction to wrap the actual function.

Lastly we need to make a command line program that takes the number (i.e. n) that we want to calculate $fib(n)$ for. As Haskell is pure and lazy, we can't simply in line system calls like we do in c. In Haskell a monadic style is chosen.

-- First argument is read and parsed as Integermain = do    a <- getArgs    putStrLn $show (fibAcc$ read (a !! 0) )

In the above example we first read the list of arguments into a, thereafter we parse the first (0th) element and calculate the corresponding Fibonacci number. The result is converted to a string and written back to the command line.

Haskell provides two ways to evaluate a program. It has its REPL (read-eval-print loop) where the file can be loaded and the program can be compiled.

$ghci Fib.hs...Ok, modules loaded: Main.*Main> fib 1055*Main> fibAcc 1055 Alternatively Haskell can be compiled and executed: $ ghc Fib.hs -o fib\$ ./fib 1055

# Functional Fibonacci

In this first implementation we used two techniques for implementing the Fibonacci function:

• Recursion: This is the typical way of thinking of problems in a functional context. In this case it has a exponential time complexity. This is bad, as we know that the Fibonacci function can be implemented faster.
• Recursion with accumulator: The idea is that we immidiatly accumulate partial results into an accumulator which is passed on to the next call. For Fibonacci we only care about the two previous results. This approach lets us forget all intermediate results and only pass forward the data we need. This lets us achieve a linear time complexity. Furthermore many compilers provide tail call optimization. In that way we have constant space consumption and do not suffer from stack overflows.