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

[Felipe Lessa]

(While writing this message GMail told me I was too late to answer the
question. Oh well, as I already typed it, let's send =)

On Jan 12, 2008 9:16 PM, Hugh Perkins <hughperkins at gmail.com> wrote:
> 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?

It *can*, but all Haskell implementations I know do not. The reason is
very simple, it would need a veery large amount of memory, and
sometimes searching to see if the answer was already calculated could
be worse than recalculating it (think of (+1) or perhaps (null)).
Polimorphic functions would also complicate the matter, as multiple
different caches would be needed.

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

If you do something like

let x = f 20 in x + x

it *probably* will be calculated only once (although it could be
calculated twice). But in the (bad) implementaion of fibonacci below,

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

when calculating (fib 40), (fib 38) will be calculated twice, (fib 37)
will be calculated thrice, etc.

-- 
Felipe.