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, <ajb@spamcop.net> wrote:
G'day all.


Quoting Andrew Coppin <andrewcoppin@btinternet.com>:

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