Hello,
> 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.
-Jeff
---
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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
