[Haskell-cafe] Sharing Subexpressions: Memoization of Fibonacci
sequence
Daniel Fischer
daniel.is.fischer at web.de
Mon Oct 12 15:55:33 EDT 2009
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
More information about the Haskell-Cafe
mailing list