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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe