[Haskell-cafe] List concat

[Lennart Augustsson]

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>
wrote:

> 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