[Haskell-beginners] Understanding cached fibonnacci function

Patrick LeBoutillier patrick.leboutillier at gmail.com
Thu Jan 29 13:18:32 EST 2009


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?


Thanks a lot,

Patrick LeBoutillier

-- 
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada


More information about the Beginners mailing list