[Haskell-beginners] Understanding cached fibonnacci function
daniel.is.fischer at web.de
Thu Jan 29 15:22:44 EST 2009
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
fibs :: [Integer]
fibs = fix ((0:) . scanl (+) 1)
More information about the Beginners