[Haskell-cafe] memoization

[Tom Ellis]

On Mon, Jul 22, 2013 at 12:02:54AM -0800, Christopher Howard wrote:
> > A binding is memoized if, ignoring everything after the equals sign,
> > it looks like a constant.
[...]
> Thanks. That's very helpful to know. Yet, it seems rather strange and
> arbitrary that "f x = ..." and "f = \x -> ..." would be treated in such
> a dramatically different manner.

This is actually rather subtle, and it's to do with desugaring of pattern
matching and where.

    f x = expression s x where s = subexpression

desugars to

    f = \x -> (let s = subexpression in expression s x)

This is not the same as

    f = expression s where s = subexpression

which desugars to

    f = let s = subexpression in (expression s)

which I think is the same as

    f = let s = subexpression in (\x -> expression s x)

In the first case a new thunk for s is created each time an argument is
applied to f.  In the second case the same thunk for s exists for all
invocations of f.

This is nothing to do with explicit memoization by the compiler, but is
simply the operational semantics of lazy evaluation in terms of thunks.

(I think I got this all right, and if not I hope someone will chime in with
a correction.  I spent some time trying to grasp this a few months ago, but
as I said it's subtle, at least to someone like me who hasn't studied lambda
calculus in depth!)

Tom