Re: 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.