[Haskell-cafe] memoization

wren ng thornton wren at freegeek.org
Tue Jul 23 01:04:33 CEST 2013


On 7/22/13 9:06 AM, Tom Ellis wrote:
> On Mon, Jul 22, 2013 at 07:52:06PM +1200, Chris Wong wrote:
>> A binding is memoized if, ignoring everything after the equals sign,
>> it looks like a constant.
>>
>> In other words, these are memoized:
> [...]
>>      f = \x -> x + 1
> [...]
>> and these are not:
>>
>>      f x = x + 1
>
> In what sense is the former memoised?  I'm not aware of any difference
> between these two definitions.

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.

-- 
Live well,
~wren





More information about the Haskell-Cafe mailing list