A Functional Fibonacci Sequence (as Learned by an Imperative Programmer)

As mentioned previously, I've been interested in learning different programming languages and paradigms, not necessarily so that I can program in those languages, but so that I can improve my everyday programming in my main language.

One of my favorite things to noodle around with is the Fibonacci Sequence. This is just complicated enough to be interesting but not too complicated to be overwhelming. The sequence is easy enough:

1, 1, 2, 3, 5, 8, 13, 21, ...

Each item in the sequence is created by adding the 2 previous numbers. The sequence can start with either 0 or 1 (I use the version that starts with 1). So, the sequence goes like this:

 1
 1 = 1 + 0
 2 = 1 + 1
 3 = 1 + 2
 5 = 2 + 3
 8 = 3 + 5
13 = 5 + 8
21 = you get the idea

This is a classic example of a sequence that would lend itself to a recursive function. In my example code, I calculate the sequence using some global variables, but that's usually because the focus of the example is not on the Fibonacci sequence itself but on the code that uses it.

A Recursive Implementation
When I started diving into Haskell, I thought that implementing a Fibonacci sequence would be a good way for me to get familiar with the language. My first implementation included 2 functions.

fibonacci :: Int -> Int
fibonacci 1 = 1
fibonacci 2 = 1
fibonacci n = fibonacci(n-1) + fibonacci(n-2)

This method takes a parameter for the position of the number in the sequence. So, for example, if we call "fibonacci 4", it will give us the 3rd number in the Fibonacci sequence (which is 3). It does this with a recursive call. Let's walk through the implementation above.

"fibonacci 4" would use the last case ("fibonacci n") and would result in the following:

fibonacci (4-1) + fibonacci (4-2)

Reduced to

fibonacci 3 + fibonacci 2

"fibonacci 2" is equal to "1". Let's put that in:

fibonacci 3 + 1

"fibonacci 3" will use the "fibonacci n" case. Let's expand that:

fibonacci (3-1) + fibonacci (3-2) + 1

or

fibonacci 2 + fibonacci 1 + 1

And since "fibonacci 2" equals 1 and "fibonacci 1" also equals 1, we're left with

1 + 1 + 1

So, the 4th item in the Fibonacci sequence is 3.

To create a sequence of these numbers, I created another recursive function:

fibonacciList :: Int -> [Int]
fibonacciList 1 = [1]
fibonacciList n = fibonacciList (n-1) ++ [fibonacci n]

To use this method, we just pass in the number of items in our Fibonacci sequence, and it returns a list with the specified number of items.

fibonacciList 8
[1,1,2,3,5,8,13,21]

This function basically builds a list based on the "fibonacci" function. So, it creates the elements of the list by running "fibonacci 1", then "fibonacci 2", "fibonacci 3", ... "fibonacci n". We won't go through the recursion step-by-step.

A Big Problem
I was pretty proud of myself when I came up with these methods. I created a Fibonacci sequence, and I did it "functionally". But these methods have a big problem.

Since the "fibonacciList" function calls "fibonacci n" for each element, it actually ends up recalculating all of the previous numbers each time. What this means is that it works fine for small lists. But once we get to slightly larger lists, we find that the calculation slows down significantly. In fact, "fibnonacci 35" takes over 20 seconds to calculate on my laptop. That seems pretty ridiculous.

I was actually working on Euler problem #2 when I ran into this performance issue. And it really bothered me. So, I started to look for other solutions to calculate the Fibonacci sequence.

Note: I talked about Euler problems when I worked through Euler problem #1 on my blog.

A Truly Functional Fibonacci
I ran across this implementation that is very simple. But since my brain isn't quite used to thinking functionally, this completely escaped me. And when I saw the solution, it took a while before I really understood what it was doing.

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The ":" operator basically creates list elements. So, when we have "1 : 1", this is the equivalent of the list "[1,1]". This function will actually create an infinite list of Fibonacci numbers (which is really interesting to run). We can wrap this in a list comprehension to return a list that stops once we get to 21.

testFibs = [x | x <- takeWhile (<= 21) fibs]
[1,1,2,3,5,8,13,21]

This works because Haskell is lazy evaluated. So even though the "fibs" list is infinite, Haskell will stop processing once it hits the takeWhile limitation that we set (<= 21).

Let's think about how "fibs" works. The "zipWith" function applies a function (in this case "+") to two lists. The lists are "fibs" (which is the current list) and "tail fibs" which includes everything but the first item. Again, this takes a bit to wrap your head around since these are recursive calls that are lazy evaluated.

It ends up creating a sort of ongoing offset list.

               [1, 1]
               [1]
         [1, 1, 2]

Here "fibs" is [1,1] and "tail fibs" is [1]. When we add these together (ignoring any "leftover" elements), we get [2] which is appended to the list.

            [1, 1, 2]
            [1, 2]
      [1, 1, 2, 3]

To get the 4th item, "fibs" is [1,1,2] and "tail fibs" is [1,2]. When we add these, we get [2, 3].

         [1, 1, 2, 3]
         [1, 2, 3]
   [1, 1, 2, 3, 5]

This continues, we can see that adding the columns from the diagram, fibs + tail fibs = the rest of the Fibonacci sequence.

      [1, 1, 2, 3, 5]
      [1, 2, 3, 5]
[1, 1, 2, 3, 5, 8]

Okay, so I don't know if the diagrams make it more clear or less clear. The combination of lazy evaluation with the recursiveness makes this quite a brain twister. But once it "clicks", it's extremely cool.

Wrap Up
So, what I've learned from this exercise is that I'll have to do a lot more work with functional programming for this to become more natural. I know that my first pass won't always be correct. But, I've found that solving a complex problem by building the solution up from smaller steps is a pretty amazing way to work.

I'll keep exploring functional programming (heading into F# soon), and I'm looking forward to making my brain think in new ways.

Happy Coding!