[prev in list] [next in list] [prev in thread] [next in thread] 

List:       haskell-cafe
Subject:    RE: [Haskell-cafe] Newbie question about automatic memoization
From:       "peterv" <bf3 () telenet ! be>
Date:       2007-07-31 19:06:23
Message-ID: 003b01c7d3a5$e321dba0$a96592e0$ () be
[Download RAW message or body]

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@jellybean.co.uk] 
Sent: Tuesday, July 31, 2007 5:09 PM
To: Bryan Burgers
Cc: peterv; haskell-cafe@haskell.org
Subject: Re: [Haskell-cafe] Newbie question about automatic memoization

Bryan Burgers wrote:
> On 7/30/07, peterv <bf3@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


[prev in list] [next in list] [prev in thread] [next in thread]