[Haskell-cafe] Memoization-question

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Fri Dec 12 09:47:34 EST 2008

Mattias Bengtsson wrote:
> The program below computes (f 27) almost instantly but if i replace the
> definition of (f n) below with (f n = f (n - 1) * f (n -1)) then it
> takes around 12s to terminate. I realize this is because the original
> version caches results and only has to calculate, for example, (f 25)
> once instead of (i guess) four times.
> There is probably a good reason why this isn't caught by the compiler.
> But I'm interested in why. Anyone care to explain?

GHC does "opportunistic CSE", when optimizations are enabled. See


I've found it very hard to predict whether this will happen or not, from
a given source code, because the optimizer will transform the program a
lot and the "opportunistic CSE" rule may apply to one of the transformed

It's best to make sharing explicit when you need it, as you did below.

> > main = print (f 27)
> > 
> > f 0 = 1
> > f n = let f' = f (n-1)
> >       in f' * f'


More information about the Haskell-Cafe mailing list