[Haskell-cafe] Memoization

[Jon Fairbairn]

On 2005-10-07 at 22:42-0000 "Gerd M" wrote:
> >As (memory) is a function, it
> >cannot be memoized (the function can be, but not its result, which is
> >what you're after).
> How can a funcion be memoized but not it's result (what does this mean)!? 
> Since there are no side effects in Haskell why is it important that the 
> array is a CAF? Or let's say it that way, why can't the results of a (pure) 
> function be memoized since it always returns the same result for the same 
> parameters?

I'm a bit rusty on this, but here's an attempt at an
explanation.

This is an implementation issue; a matter of choice for the
implementor. In a function like this:

> f x = factorial 100 + x

"factorial 100" doesn't depend on x -- is a CAF -- so it can
be lifted out and computed only once. Note that since the
value of f doesn't depend on whether this is done, there's
no /requirement/ that the compiler do it.

In this:

> g a = \ x -> factorial a + x

g 100 is equivalent to f, but here the factorial 100 isn't a
constant (it depends on a), so the compiler would have to go
to extra lengths (known as "full laziness") to ensure that
the factorial was kept for each application of g. It's
certainly possible for a compiler to do this, but the
problem is that if the subexpression that gets retained is
infinite, it takes up a lot of space, and there's no way for
the programmer to say that it's no longer needed. So
compilers tend not to do this.

  Jón


-- 
Jón Fairbairn                              Jon.Fairbairn at cl.cam.ac.uk