[Haskell-cafe] memoization

Tom Ellis tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk
Tue Jul 23 08:27:18 CEST 2013

On Mon, Jul 22, 2013 at 04:04:33PM -0700, wren ng thornton wrote:
> Consider rather,
>     f1 = let y = blah blah in \x -> x + y
>     f2  x = let y = blah blah in x + y
> The former will memoize y and share it across all invocations of f1;
> whereas f2 will recompute y for each invocation.


> In principle, we could translate between these two forms (the f2 ==> f1
> direction requires detecting that y does not depend on x). However, in
> practice, the compiler has no way to decide which one is better since it
> involves a space/time tradeoff which: (a) requires the language to keep
> track of space and time costs, (b) would require whole-program analysis to
> determine the total space/time costs, and (c) requires the user's
> objective function to know how to weight the tradeoff ratio.

This is called the full laziness transformation


and indeed with optimization on GHC (sometimes) does it, even when not appropriate



More information about the Haskell-Cafe mailing list