Andrew Coppin 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?


See also Data.Sequence, which is not O(1) append, but it is O(log something), and also O(1) cons and snoc and has lots of other nice complexities including fast update of a single cell.

Jules
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to