[Haskell-cafe] List concat

[Derek Elkins]

On Mon, 2008-05-12 at 02:36 -0400, 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.

I think we can safely simplify that to O(k) (at least for sequential
programs).