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?
Hi
data List a = Zero | One a | Two (List a) (List a)
On Fri, May 9, 2008 at 3:16 PM, Andrew Coppin
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
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.
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. Jules
There are many implementations of such things. Data.Sequence is one. You
can also make an implementation that has O(1) cons, snoc, and append, but
that's rather tricky and has a large constant factor.
-- Lennart
On Fri, May 9, 2008 at 3:16 PM, Andrew Coppin
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?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Lennart Augustsson wrote:
There are many implementations of such things. Data.Sequence is one. You can also make an implementation that has O(1) cons, snoc, and append, but that's rather tricky and has a large constant factor.
Ah. So not only is it possible, but it's already in a standard library. I had a feeling this might be the case...
On Fri, May 09, 2008 at 11:04:26PM +0100, Lennart Augustsson wrote:
There are many implementations of such things. Data.Sequence is one. You can also make an implementation that has O(1) cons, snoc, and append, but that's rather tricky and has a large constant factor.
It's also rather difficult to construct a use case that distinguishes between O(1) and O(log(min(n1,n2))) append. For example, building a sequence with either sort of append takes linear time. The constant factors are everything.
participants (7)
-
ajb＠spamcop.net -
Andrew Coppin -
Jeff Polakow -
Jules Bean -
Lennart Augustsson -
Neil Mitchell -
Ross Paterson