[Haskell-beginners] Relying on memoization

[Daniel Fischer]

On Fri, Dec 10, 2010 at 5:39 AM, Russ Abbott <russ.abbott at gmail.com> 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 *
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20101210/41c85144/attachment.htm>