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

[Thomas Davie]

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?)
>>
>> 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