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.

OK, what's happening is that in Hugs, functions that return one of their
arguments, like

	min x y = if x <= y then x else y

return an indirection to the argument (to avoid copying it), so these
examples traverse a chain of indirections that gets longer for each
new min, hence the quadratic behaviour.

This is now fixed in CVS (no need to create an indirection pointing at
an indirection).  Thanks for the analysis.