Haskell: Why is my implementation of the Fibonacci sequence inefficient?
I wrote the following Fibonacci game program as part of learning Haskell:
fibonacci 0 = [0]
fibonacci 1 = [0,1]
fibonacci n = let
foo'1 = last (fibonacci (n-1))
foo'2 = last (fibonacci (n-2))
in reverse((foo'1 + foo'2):reverse (fibonacci (n-1)))
The program works:
ghci>fibonacci 6
[0,1,1,2,3,5,8]
But performance declines exponentially with n. If I give it an argument at 30, it takes about a minute to run, rather than running instantly at 6. It seems like lazy execution is burning me up and Fibonacci is triggered once for each item in the final list.
Am I doing something stupid or missing something?
(I already got rid of the ++ thinking that could do this)
source to share
As pointed out in the comments, your approach is a little more complicated. In particular, you don't need to use recursive calls or even a function reverse
to generate the Fibonacci sequence.
Linear implementation
In addition to your own answer , here is a one-layer tutorial that uses memoization:
fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Once you have it fibs
, writing your function is fib
trivial:
fib :: Int -> [Integer] fib n | n < 0 = error "fib: negative argument" | otherwise = take (n+1) fibs
This implementation fib
has a complexity of Θ (n), which is obviously much better than Θ (exp (n)).
Test at GHCi
λ> :set +s λ> fib 6 [0,1,1,2,3,5,8] (0.02 secs, 7282592 bytes) λ> fib 30 [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040] (0.01 secs, 1035344 bytes)
As you can see it fib 30
is estimated within one minute on my machine.
Further reading
For a more in-depth look at how to generate a Fibonacci sequence in Haskell, I refer you to this haskell.org wiki
source to share
Here's an answer to the question using @icktoofay pointer for memoization . The answer included a function that quickly returned a given Fibonacci number, so I used their example to create a solution to my original problem - creating a list of Fibonacci numbers with the requested number.
This solution works pretty quickly (the page has the added benefit of referring to my approach as "naive")
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
where fib 0 = 0
fib 1 = 1
fib n = memoized_fib (n-2) + memoized_fib (n-1)
fib 0 = [0]
fib 1 = [0,1]
fib n = reverse ((memoized_fib (n-2) + memoized_fib(n-1)) : reverse (fib (n-1)))
source to share
You don't need to add memoization to your function - it already has all of the previous results, creating a list like it does. You just need to stop ignoring these results like you are using now last
.
First of all, if it is more natural to create the list in reverse order, there is no reason not:
revFib 0 = [0]
revFib 1 = [1,0]
revFib n | n > 0 = let f1 = head (revFib (n-1))
f2 = head (revFib (n-2))
in f1 + f2 : revFib (n-1)
This is still slow because we are still ignoring all previous results except for the very last one at the top of the list. We can stop doing this
revFib 0 = [0]
revFib 1 = [1,0]
revFib n | n > 0 = let f1 = head (revFib (n-1))
f2 = head (tail (revFib (n-1)))
in f1 + f2 : revFib (n-1)
and then we'll name the generic subexpression to be generic to use it and it is evaluated only once:
revFib 0 = [0]
revFib 1 = [1,0]
revFib n | n > 0 = let prevs = revFib (n-1)
[f1,f2] = take 2 prevs
in f1 + f2 : prevs
and suddenly it's linear, not exponential.
source to share