[Haskell-cafe] Memoization

[Gerd M]

Thanks to everyone for the answers, I'm getting a picture now. Maybe I will 
give the memoizing Y combinator a try later.

>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
>
>

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE! 
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/