# Understanding cached fibonnacci function

 Classic List Threaded
2 messages
Reply | Threaded
Open this post in threaded view
|

## Understanding cached fibonnacci function

 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
Reply | Threaded
Open this post in threaded view
|

## Understanding cached fibonnacci function

 I don't know exactly how to explain it, but it has to do with memoization The first version generates a fully memoized function, while the second creates a memoized version for each call, since the thunk and memoization for fib is destroyed after each computation. This is not a precise explanation, but I can't think of a better way to put it... On Thu, Jan 29, 2009 at 16:18, Patrick LeBoutillier < [hidden email]> 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? > > > Thanks a lot, > > Patrick LeBoutillier > > -- > ===================== > Patrick LeBoutillier > Rosem?re, Qu?bec, Canada > _______________________________________________ > Beginners mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/beginners> -- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc. -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20090130/548aedb7/attachment.htm