[Haskell-cafe] Newbie question about automatic memoization

[Bulat Ziganshin]

Hello peterv,

Tuesday, July 31, 2007, 11:06:23 PM, you wrote:

it is property of explicit *name* given to result of some expression.
for example, when you write

f x = g (x*x) (x*x)

result of x*x isn't stored because it may be very large and compiler
exactly follows your instruction - "calculate x*x two times" without
trying to do optimization that may turn out to pessimization (of
course, i mean that with *lazy* evaluation x*x is calculated only when
needed and it may become a pessimization to save value between its
usages as first and second argument)

when you write

f x = g t t where t=x*x

compiler gets an instruction to calculate x*x only once and share
calculated value between two parameters and it does just what you said

> Thanks! Is this is also the case when using let and where, or is this just
> syntactic sugar?

> -----Original Message-----
> From: Jules Bean [mailto:jules at jellybean.co.uk] 
> Sent: Tuesday, July 31, 2007 5:09 PM
> To: Bryan Burgers
> Cc: peterv; haskell-cafe at haskell.org
> Subject: Re: [Haskell-cafe] Newbie question about automatic memoization

> Bryan Burgers wrote:
>> On 7/30/07, peterv <bf3 at telenet.be> wrote:
>>> Does Haskell support any form of automatic memorization?
>>>
>>> For example, does the function
>>>
>>>         iterate f x
>>>
>>> which expands to
>>>
>>>         [x, f(x), f(f(x)), f(f(f(x))), .
>>>
>>> gets slower and slower each iteration, or can it take advantage of the
> fact
>>> that f is referentially transparent and hence can be "memoized / cached"?
>>>
>>> Thanks,
>>> Peter
>> 
>> For 'iterate' the answer does not really need to be memoized.

> Or, another way of phrasing that answer is 'yes'. The definition of 
> iteration does memoize - although normally one would say 'share' - the
> intermediate results.

>> 
>> I imagine the definition of 'iterate' looks something like this:
>> 
>> iterate f x = x : iterate f (f x)
>> 

> Haskell doesn't automatically memoize. But you are entitled to assume 
> that named values are 'shared' rather than calculated twice. For 
> example, in the above expression "x", being a named value, is shared 
> between (a) the head of the list and (b) the parameter of the function
> "f" inside the recursive call to iterate.

> Of course sharing "x" may not seem very interesting, on the outermost 
> call, but notice that on the next call the new "x" is the old "f x", and
> on the call after that the new "x" is "f (f x)" w.r.t the original "x".

> Jules

> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com