[Haskell-cafe] List concat

Jules Bean jules at jellybean.co.uk
Fri May 9 10:31:31 EDT 2008

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.


More information about the Haskell-Cafe mailing list