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
