[Haskell-cafe] List concat

[Lennart Augustsson]

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 at spamcop.net> wrote:

> G'day all.
>
> Quoting Andrew Coppin <andrewcoppin at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080512/3af77b50/attachment.htm