[Haskell-beginners] Understanding cached fibonnacci function

[Daniel Fischer]

Am Donnerstag, 29. Januar 2009 20:29 schrieb Thomas Davie:
>
> 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.

However, if you compile it with -O2, the optimiser sees it's better to keep 
the list and it's again a linear time algorithm.

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

I meet fibs !! 0 == 0 more often.

>
> 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

Not to forget the marvellous

import Control.Monad.Fix

fibs :: [Integer]
fibs = fix ((0:) . scanl (+) 1)

>
> Bob