[Haskell-cafe] List concat

Andrew Coppin andrewcoppin at btinternet.com
Fri May 9 10:16:28 EDT 2008

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?

More information about the Haskell-Cafe mailing list