[Haskell-beginners] Relying on memoization

[Russ Abbott]

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 at googlemail.com> wrote:

>
>
> 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/91428d84/attachment.htm>