[Haskell-cafe] [newbie question] Memoization automatic in Haskell?
tom.davie at gmail.com
Sat Jan 12 18:22:41 EST 2008
On 12 Jan 2008, at 23:16, Hugh Perkins wrote:
> On Jan 12, 2008 10:54 PM, Henning Thielemann
> <lemming at henning-thielemann.de> wrote:
>> On Sat, 12 Jan 2008, Hugh Perkins wrote:
>>> I guess that Haskell's referential transparence means the answers to
>>> the isPerfectSquare will be cached, ie automatically memoized? (not
>>> sure if is correct term?)
> Interesting... but I dont understand... I thought that referential
> transparence meant that once the answer to a function has been
> calculated once, it will always be the same, and that the interpreter
> can, and will, cache this answer?
> So, if I call f( 20 ) once, for some, arbitrary, f, it will have to go
> away and calculate f(20), but if I call it multiple times, it will
> just return the value it already calculated?
Memorisation has it's costs too... Suppose you wanted to computer
map f [1..100000000000000]? Each time f was called, your program
would look up a table of on average 50000000000000 results for f.
That doesn't sound very efficient if f is a simple function. Now
suppose you're running a program for several hours -- imagine how
large your table would become, and how slow your lookup would be.
What you can do however, is introduced constants. Constants are
evaluated once and only once, so using them, you can tell the compiler
exactly what should be memorized.
More information about the Haskell-Cafe