[Hugs-users] trivial list foldings require quadratic time?

[Härmel Nestra]

Hi,

Recently I noticed that evaluating
minimum [1 .. 10000]
in Hugs takes much more time than evaluating
minimum [10000, 9999 .. 1]
.

This seems weird because evaluating  min  always needs evaluation of 
both its arguments, so the computation schema should be the same.
I think this is a bug.

Making experiments with the length varying leads to the suggestion that
minimum [1 .. n]
runs in quadratic time on  n  while
minimum [n, n - 1 .. 1]
runs in linear time.

But it would be normal to assume  minimum  working in linear time in both
cases. By the way, both the number of reductions and the number of cells
reported by Hugs grow linearly in both cases, the corresponding numbers
remain close to each other. 

Somehow the reductions of  minimum [1 .. 10000]  take much more time on an
average then the reductions of  minimum [10000, 9999 .. 1] . The difference
is that, in the first case, comparisions are performed with the same element
1 all the time while, in the second case, the numbers being compared
continuously change.

I made yet more experiments. From the expressions
foldl (\ x y -> if x < y then x else y) (maxBound :: Int) [1 .. 10000]
foldl (\ x y -> if x < y then x else y) (maxBound :: Int) [10000, 9999 .. 1]
foldr (\ x y -> if x < y then x else y) (maxBound :: Int) [1 .. 10000]
foldr (\ x y -> if x < y then x else y) (maxBound :: Int) [10000, 9999 .. 1]
the first and the last evaluate slowly while the others evaluate fast,
although evaluation of the last needs by ~20% less reductions and cells than
the third.

The phenomenon occurs even when using  foldl'  instead of  foldl .

The punch-line is that if I modify the expressions as follows:
foldl (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [1 .. 10000]
foldl (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [10000, 9999 .. 1]
foldr (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [1 .. 10000]
foldr (\ x y -> if x < y then x + 0 else y + 0) (maxBound :: Int) [10000, 9999 .. 1]
then all are fast!

The conditional in the operator is not essential:
foldl (\ x y -> x) 0 [1 .. 10000]
evaluates fast,
foldl (\ x y -> ($!) const x y) 0 [1 .. 10000]
evaluates slowly,
foldl (\ x y -> ($!) const (x + 0) y) 0 [1 .. 10000]
evaluates fast again.

All this occurs with both Nov-2003 and Mar-2005 release of Hugs, on both 
Linux and Solaris. I have not tested in Windows.

With ghci, this anomaly does not appear.

Härmel