Hi data List a = Zero | One a | Two (List a) (List a)
On Fri, May 9, 2008 at 3:16 PM, Andrew Coppin <[EMAIL PROTECTED]> wrote: > The function (++) :: [x] -> [x] -> [x] has O(n) complexity. (++) = Two -- O(1) 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? Yes. Me, last month. http://www.cs.york.ac.uk/fp/darcs/uniplate/Data/Generics/Str.hs I wasn't the first though - it's been in Lava for years as well, which is where I got my inspiration. Thanks Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
