On 9/15/10, Alex Rozenshteyn
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