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

[Reid Barton]

On Mon, Oct 12, 2009 at 11:52:30AM -0700, SimonK77 wrote:
> 
> **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 ..] !!)
> ...
> I can't see where the sharing of subexpressions happens here. Any help is
> highly appreciated.

This is an excellent and subtle question.  The sharing behavior of the
code depends on the desugaring of the syntax (map fib [0 ..] !!): is it
  (!!) (map fib [0 ..])
or
  (\x -> map fib [0 ..] !! x)

I suggest, as an exercise, tracing the evaluation of memoized_fib
using each of these desugarings, and then trying them out in ghci.
Then you'll be able to tell which desugaring ghc is using.  (It's not
the one used in the Report!  In principle this is a bug since we can
distinguish them using seq.)

Regards,
Reid Barton