[Haskell-beginners] Understanding cached fibonnacci function

[Thomas Davie]

On 29 Jan 2009, at 19:46, Patrick LeBoutillier wrote:

> Hi all,
>
> I recently stumbled on this example in some wiki:
>
> mfib :: Int -> Integer
> mfib = (map fib [0 ..] !!)
>  where fib 0 = 0
>        fib 1 = 1
>        fib n = mfib (n-2) + mfib (n-1)
>
> I don't understand how the results get cached. When mfib is
> recursively called, doesn't a new (map fib [0 ..] !!) start over
> again? Or perhaps I'm thinking too imperatively here...
>
> Also, if I change the definition to this (adding "a" on both sides):
>
> mfib :: Int -> Integer
> mfib a = (map fib [0 ..] !!) a
>  where fib 0 = 0
>        fib 1 = 1
>        fib n = mfib (n-2) + mfib (n-1)
>
> the funtion becomes slow again. Why is that?

The reason that the second one is slower is that ghc makes a  
distinction that so called CAFs (constant applicative forms) are  
likely to be constants, and evaluates them once.  Thus, your list (map  
fib [0..]) gets kept between runs.  In the second form though, ghc  
sees a function, and evaluates it every time it gets called, which  
makes it into an exponential time algorithm.

An aside:  fibs !! 0 is usually defined to be 1.

Here's another couple of definitions of fib for you to play with, and  
try and figure out the properties of:
mfib :: Int -> Integer
mfib = ((fibs  1 1) !!)

fibs :: Integer -> Integer -> [Integer]
fibs n m = n : fibs m (n+m)

-- and
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Have fun

Bob