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

On Mon, Feb 13, 2006 at 08:21:04PM +0200, Härmel Nestra wrote:

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.

Great stuff! More experiments, expanding the arithmetic sequences: slow: foldr min 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int foldr max 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int foldl min 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int fast: foldl max 0 (takeWhile (<= 10000) (iterate (+1) 1)) :: Int and even if we share the input to the folds. It seems that a shared redex isn't being updated by max/min and similar functions.