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