Re[2]: [Haskell-cafe] Newbie question about automatic memoization
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:[EMAIL PROTECTED] > 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 <[EMAIL PROTECTED]> 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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Newbie question about automatic memoization
Thanks! Is this is also the case when using let and where, or is this just syntactic sugar? -Original Message- From: Jules Bean [mailto:[EMAIL PROTECTED] 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 <[EMAIL PROTECTED]> 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question about automatic memoization
Bryan Burgers wrote: On 7/30/07, peterv <[EMAIL PROTECTED]> 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Newbie question about automatic memoization
On 7/30/07, peterv <[EMAIL PROTECTED]> 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. I imagine the definition of 'iterate' looks something like this: iterate f x = x : iterate f (f x) So f isn't being applied n times to x for the n+1st element, rather, it's being applied once to the nth element for the n+1st element. Bryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Newbie question about automatic memoization
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 No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.5.476 / Virus Database: 269.10.25/926 - Release Date: 29/07/2007 23:14 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe