Re: Reduction count as efficiency measure?

[Amr A Sabry]

> 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?

I haven't tried in ghc, hbc, and Hugs specifically but it is a
possible scenario. Consider:

max [] = 0
max(x:xs) = if (x > (max xs)) then x else (max xs) 

max [1,2,3,4,5]

An evaluator (presumably a non-optimizing interpreter) that doesn't
lift the common subexpression (max xs) will require exponential time
to compute the maximum of an ordered list. An optimizing compiler that
shares the common subexpression will produce code that runs in linear
time. --Amr