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

12 Oct 2009

      Am Montag 12 Oktober 2009 21:09:38 schrieb minh thu:
...
2009/10/12 SimonK77 :
...
**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

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

Daniel Fischer