After writing the previous post, it struck me that memoization could be done at the function level. If each function had an associated Map <Arguments> <Result>, lookup would be much simpler and more localized. One could then decide on a function-by-function basis which maps to expand. * -- Russ * On Fri, Dec 10, 2010 at 1:16 AM, Daniel Fischer < daniel.is.fischer@googlemail.com> wrote:

On Fri, Dec 10, 2010 at 5:39 AM, Russ Abbott wrote:

...

(Is that even the right term?)

Yes.

...

Let's suppose I have a fairly complex computation to perform on a data structure. Normally I would cache the computed value in a field of the structure. The next time I need it I don't have to compute it again. (Of course if the structure changes, I have to recompute the value and store it again.)

In Haskell is it the case that caching of this sort is redundant since Haskell does it for me? That is, if I call

f someStructure

multiple times at different places in my code and if both "f" and "someStructure" refer to the same things each time, can I rely on Haskell not to perform the computation multiple times but to look up the result it previously computed?

No, you can't rely on that, and in general f someStructure will be computed multiple times. If two "f someStructure" appear in the same expression, there's a chance they will be shared, but you can't rely on it. It's very hard to determine when sharing common subexpressions is beneficial and when it's detrimental, so at least in GHC, common subexpression elimination is not done much. If you want something to be shared, give it a name in the enclosing scope, the value that name is bound to will be computed only once (unless polymorphism prevents sharing and forces the value to be recomputed).

...

Is there some limit to that? If every computation is stored, doesn't that create a very large collection of stored results?

Right, and apart from needing a lot of memory, storing everything makes finding the cached result slower than recomputing it in many cases.

...

* -- Russ *