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