[Haskell-beginners] Understanding cached fibonnacci function
Thomas Davie
tom.davie at gmail.com
Thu Jan 29 14:29:35 EST 2009
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
More information about the Beginners
mailing list