Haskell inefficient fibonacci implementation

Question

I am new to haskell and just learning the fun of functional programming. but have run into trouble right away with an implementation of the fibonacci function. Please find the code below.

--fibonacci :: Num -> [Num]
fibonacci 1 = [1]
fibonacci 2 = [1,1]
--fibonacci 3 = [2]
--fibonacci n = fibonacci n-1
fibonacci n = fibonacci (n-1) ++ [last(fibonacci (n-1)) + last(fibonacci (n-2))]

Rather awkward, I know. I can't find time to look up and write a better one. Though I wonder what makes this so inefficient. I know I should look it up, just hoping someone would feel the need to be pedagogic and spare me the effort.

Answer 1

orangegoat's answer and Sec Oe's answer contain a link to probably the best place to learn how to properly write the fibonacci sequence in Haskell, but here's some reasons why your code is inefficient (note, your code is not that different from the classic naive definition. Elegant? Sure. Efficient? Goodness, no):

Let's consider what happens when you call

fibonacci 5

That expands into

(fibonacci 4) ++ [(last (fibonacci 4)) + (last (fibonacci 3))]

In addition to concatenating two lists together with ++, we can already see that one place we're being inefficient is that we calculate fibonacci 4 twice (the two places we called fibonacci (n-1). But it gets worst.

Everywhere it says fibonacci 4, that expands into

(fibonacci 3) ++ [(last (fibonacci 3)) + (last (fibonacci 2))]

And everywhere it says fibonacci 3, that expands into

(fibonacci 2) ++ [(last (fibonacci 2)) + (last (fibonacci 1))]

Clearly, this naive definition has a lot of repeated computations, and it only gets worse when n gets bigger and bigger (say, 1000). fibonacci is not a list, it just returns lists, so it isn't going to magically memoize the results of the previous computations.

Additionally, by using last, you have to navigate through the list to get its last element, which adds on top of the problems with this recursive definition (remember, lists in Haskell don't support constant time random access--they aren't dynamic arrays, they are linked lists).

---

One example of a recursive definition (from the links mentioned) that does keep down on the computations is this:

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

Here, fibs is actually a list, and we can take advantage of Haskell's lazy evaluation to generate fibs and tail fibs as needed, while the previous computations are still stored inside of fibs. And to get the first five numbers, it's as simple as:

take 5 fibs -- [0,1,1,2,3]

(Optionally, you can replace the first 0 with a 1 if you want the sequence to start at 1).

Answer 2

All the ways to implement the fibonacci sequence in Haskell just follow the link http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

Answer 3

This implementation is inefficient because it makes three recursive calls. If we were to write a recurrence relation for computing fibonacci n to a normal form (note, pedantic readers: not whnf), it would look like:

T(1) = c
T(2) = c'
T(n) = T(n-1) + T(n-1) + T(n-2) + c''

(Here c, c', and c'' are some constants that we don't know.) Here's a recurrence which is smaller:

S(1) = min(c, c')
S(n) = 2 * S(n-1)

...but this recurrence has a nice easy closed form, namely S(n) = min(c, c') * 2^(n-1): it's exponential! Bad news.

I like the general idea of your implementation (that is, track the second-to-last and last terms of the sequence together), but you fell down by recursively calling fibonacci multiple times, when that's totally unnecessary. Here's a version that fixes that mistake:

fibonacci 1 = [1]
fibonacci 2 = [1,1]
fibonacci n = case fibonacci (n-1) of
    all@(last:secondLast:_) -> (last + secondLast) : all

This version should be significantly faster. As an optimization, it produces the list in reverse order, but the most important optimization here was making only one recursive call, not building the list efficiently.

Answer 4

So even if you wouldn't know about the more efficient ways, how could you improve your solution?

First, looking at the signature it seems you don't want an infinite list, but a list of a given length. That's fine, the infinite stuff might be too crazy for you right now.

The second observation is that you need to access the end of the list quite often in your version, which is bad. So here is a trick which is often useful when working with lists: Write a version that work backwards:

fibRev 0 = []
fibRev 1 = [1]
fibRev 2 = [1,1]
fibRev n = let zs@(x:y:_) = fibRev (n-1) in (x+y) : zs

Here is how the last case works: We get the list which is one element shorter and call it zs. At the same time we match against the pattern (x:y:_) (this use of @ is called an as-pattern). This gives us the first two elements of that list. To calculate the next value of the sequence, we have just to add these elements. We just put the sum (x+y) in front of the list zs we already got.

Now we have the fibonacci list, but it is backwards. No problem, just use reverse:

fibonacci :: Int -> [Int]
fibonacci n = reverse (fibRev n)

The reverse function isn't that expensive, and we call it here only one time.