RE: Reduction count as efficiency measure?

[Simon Peyton-Jones]

> I'm still curious about my first question, though, about the specific
> optimizations included in ghc and hbc.  If in fact they don't do CSE,
> are there optimizations which they do perform which would change the
> asymptotic running time?

GHC doesn't do CSE, and this is part of the reason... generally
I don't think that compilers should change asymptotic running time.
CSE can also make space consumption asymptotically worse.

Having said that, full laziness (which GHC does do) can change
asymptotic running time.  Consider

        f n = let g m = h n + m
                in sum (map g [1..n])

where h is linear in n.  The running time is n**2, but if you
lift out the invariant (h n) from the inside of g, you get back
to linear.

Simon