[Haskell-cafe] Sharing Subexpressions: Memoization of Fibonacci sequence

[Daniel Fischer]

Am Montag 12 Oktober 2009 21:09:38 schrieb minh thu:
> 2009/10/12 SimonK77 <simonkaltenbacher at googlemail.com>:
> > **Edit: formatting was bad**
> >
> > Hallo everyone,
> >
> > the last few weeks I was trying to get used to memoization in haskell. As
> > I found out in a previous post, memoization in haskell is, due to the
> > graph reduction strategy used in haskell, almost always implemented by
> > sharing subexpressions in an expression.
> >
> > In examples as the following this is quite easy to see.
> >
> > fibs = 0:1:zipWith (+) fibs (tail fibs)
> >
> > But as I browsed through the search results from google for this topic, I
> > encountered the following implementation:
> >
> > memoized_fib :: Int -> Integer
> > memoized_fib =
> >   let fib 0 = 0
> >       fib 1 = 1
> >       fib n = memoized_fib (n-2) + memoized_fib (n-1)
> >   in  (map fib [0 ..] !!)
> >
> > You'll find it at Haskell.org. Here's the
> > http://www.haskell.org/haskellwiki/Memoization link
> >
> > Let's assume we have the following implementation of the
> > higher-order-function map:
> >
> > map :: (a -> b) -> [a] -> [b]
> > map _ [] = []
> > map f (x:xs) = f x : map f xs
> >
> > The reduction sequence of memoized_fib 5 would start as follows:
> >
> > //Reduction of memoized_fib 5
> >
> > memoized_fib 5 = (map fib [0..] !!) 5
> >                   = (fib 0 : map fib [1..] !!) 5
> >                   = (0 : fib 1 : map fib [2..] !!) 5
> >                   = (0 : 1 : fib 2 : map fib [3..] !!) 5
> >                   = (0 : 1 : (memoized_fib 0 + memoized_fib 1) : fib 3 :
> > map fib [4..] !!) 5
> >                   = (0 : 1 : (map fib [0..] !! 0 + map fib [0..] !! 1) :
> > (memoized_fib 1 + memoized_fib 2) : map fib [4..] !!) 5
> >                        .
> >                        .
> >                        .
> >                        .
> >                   and so on!
>
> Hi,
>
> Instead of repeating as-is
>   map fib [0..]
> consider it as a single list that is always reused. Since the list
> maps the input of the fib function to the result of the function and
> that list is always reused, the recursive calls have immediately the
> answer (i.e. at the cost of the lookup).

Yes, since memoized_fib is bound by a simple pattern binding and not a function binding, 
the list is shared among different invocations of memoized_fib, same as if it was given an 
explicit name.

You can see it by adding tracing output:

import Debug.Trace

tfib :: Int -> Integer
tfib =
    let fib 0 = 0
        fib 1 = 1
        fib n = trace ("eval fib " ++ show n) $ tfib (n-2) + tfib (n-1)
    in (map fib [0 .. ] !!)

*MFib> tfib 6
eval fib 6
eval fib 4
eval fib 2
eval fib 3
eval fib 5
8
(0.00 secs, 538564 bytes)
*MFib> tfib 10
eval fib 10
eval fib 8
eval fib 7
eval fib 9
55
(0.00 secs, 0 bytes)

>
> So your fragment
>
> (0 : 1 : (map fib [0..] !! 0 + map fib [0..] !! 1)  ...
>
> should look like
>
> lst = (0 : 1 : (lst !! 0 + lst !! 1) ...
>
> which is similar to the zipWith (+) version.

Except it's much slower.

>
> Cheers,
> Thu