[Haskell-cafe] List concat

Jeff Polakow jeff.polakow at db.com
Fri May 9 10:27:25 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?
You can also do this with a functional representation of lists (i.e. lists 
are functions); this idea is usually called difference lists. There is a 
nice dlist library on hackage.



This e-mail may contain confidential and/or privileged information. If you 
are not the intended recipient (or have received this e-mail in error) 
please notify the sender immediately and destroy this e-mail. Any 
unauthorized copying, disclosure or distribution of the material in this 
e-mail is strictly forbidden.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080509/89049035/attachment.htm

More information about the Haskell-Cafe mailing list