[Haskell-cafe] List concat

ajb at spamcop.net ajb at spamcop.net
Mon May 12 02:36:14 EDT 2008

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

More information about the Haskell-Cafe mailing list