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 _______________________________________________ Hugs-Users mailing list Hugs-Users@haskell.org http://www.haskell.org/mailman/listinfo/hugs-users
