[Haskell-cafe] List concat

Lennart Augustsson lennart at augustsson.net
Fri May 9 18:04:26 EDT 2008

There are many implementations of such things.  Data.Sequence is one.  You
can also make an implementation that has O(1) cons, snoc, and append, but
that's rather tricky and has a large constant factor.

  -- Lennart

On Fri, May 9, 2008 at 3:16 PM, Andrew Coppin <andrewcoppin at btinternet.com>

> The function (++) :: [x] -> [x] -> [x] has O(n) complexity.
> If somebody were to invent some type that looks like [x] but actually uses
> some sort of tree rather than a linked list, you should be able to get O(1)
> concatenation. Has anybody ever implemented such a thing?
> _______________________________________________
> 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/20080509/17f81e1f/attachment.htm

More information about the Haskell-Cafe mailing list