Re: [Haskell-cafe] List concat

Well, if you want to be picky evaluating (calling) (xs ++ ys) takes whatever time it takes to evaluate xs to WHNF and if xs is null then it in addition takes the time it takes to evaluate ys to WHNF. Saying anything about time complexity with lazy evaluation requires a lot of context to be exact. -- Lennart On Mon, May 12, 2008 at 7:36 AM, wrote:

G'day all.

Quoting Andrew Coppin :

The function (++) :: [x] -> [x] -> [x] has O(n) complexity.

...

That's not entirely true.

When you call (++), it does O(1) work. If you evaluate k cons cells. it takes O(min(k,n)) work.

Cheers, Andrew Bromage

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe