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 <[EMAIL PROTECTED]> 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
