Re: [Haskell-cafe] [newbie question] Memoization automatic in Haskell?

On 12 Jan 2008, at 23:16, Hugh Perkins wrote:

On Jan 12, 2008 10:54 PM, Henning Thielemann 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?)

http://www.haskell.org/haskellwiki/Memoization

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?

No, 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. Bob