Understanding cached fibonnacci function

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Understanding cached fibonnacci function

Patrick LeBoutillier
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

Rafael Gustavo da Cunha Pereira Pinto-2
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