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

[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).

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.

Cheers,
Thu