[Haskell-cafe] List concat
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.
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe