[Haskell-cafe] List concat
lennart at augustsson.net
Mon May 12 17:07:21 EDT 2008
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.
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.
> Andrew Bromage
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe