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