[Haskell-cafe] Memoization/call-by-need

[Tim Chevalier]

On 9/15/10, Alex Rozenshteyn <rpglover64 at gmail.com> wrote:
> I feel that there is something that I don't understand completely:  I have
> been told that Haskell does not memoize function call, e.g.
> > slowFib 50
> will run just as slowly each time it is called.  However, I have read that
> Haskell has call-by-need semantics, which were described as "lazy evaluation
> with memoization"
>
> I understand that
> > fib50 = slowFib 50
> will take a while to run the first time but be instant each subsequent call;
> does this count as memoization?
>

Hi, Alex --

Haskell's informal semantics dictate that if we evaluate the expression:

let fib50 = slowFib 50 in
  fib50 + fib50

then the expression (slowFib 50) will be evaluated only once, not
twice, because it has a name. On the other hand, if you wrote:

let fib50 = slowFib 50 in
  fib50 + (slowFib 50)

then (slowFib 50) would be evaluated twice, because there's no
principle requiring the compiler to notice that (slowFib 50) is the
same expression as the one bound to fib50.

An optimization called "full laziness" can accomplish the kind of
stronger memoization you were suggesting in some cases, but GHC
doesn't do it consistently, as it can make performance worse.

Cheers,
Tim

-- 
Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt
"Both of them are to world religions what JavaScript is to programming
languages." -- Juli Mallett, on Satanism and Wicca