| Is this true in practice? That is, are there programs which have
| different asymptotic running times when compiled under ghc or hbc than
| when running under Hugs?
|
| It would actually surprise me if there were; I'm having a hard time
| imagining a realistic optimization that would do this. (Which could
| easily be a failure of my imagination.)
What about common subexpression elimination? AFAIK neither Hugs nor GHC
nor HBC implement CSE, but if they did the asymptotic running time
could sometimes radically change. Here is a nice example several
first-year students came up with when I asked them to program `maximum'.
> maximum [a] = a
> maximum (a : as) = if a < maximum as then maximum as else a
Thus implemented `maximum' has an exponential running time. Eliminating
the double call `maximum as' yields a linear implementation.
> maximum [a] = a
> maximum (a : as) = let m = maximum as in if a < m then m else a
Does this example convince you?
Cheers, Ralf
