List concat
|
View:
New views
10 Messages
—
Rating Filter:
Alert me
|
 |
List concat
by Andrew Coppin
::
Rate this Message:
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@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by Neil Mitchell
::
Rate this Message:
Hi
data List a = Zero | One a | Two (List a) (List a) On Fri, May 9, 2008 at 3:16 PM, Andrew Coppin <andrewcoppin@...> 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@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by Jeff Polakow
::
Rate this Message:
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@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by Jules Bean
::
Rate this Message:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by Lennart Augustsson
::
Rate this Message:
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 <andrewcoppin@...> wrote: The function (++) :: [x] -> [x] -> [x] has O(n) complexity. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by Andrew Coppin
::
Rate this Message:
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... _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by Ross Paterson
::
Rate this Message:
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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by ajb-2
::
Rate this Message:
G'day all.
Quoting Andrew Coppin <andrewcoppin@...>: > The function (++) :: [x] -> [x] -> [x] has O(n) complexity. That's not entirely true. When you call (++), it does O(1) work. If you evaluate k cons cells. it takes O(min(k,n)) work. Cheers, Andrew Bromage _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
Re: List concat
by Derek Elkins
::
Rate this Message:
On Mon, 2008-05-12 at 02:36 -0400, ajb@... wrote:
> G'day all. > > Quoting Andrew Coppin <andrewcoppin@...>: > > > The function (++) :: [x] -> [x] -> [x] has O(n) complexity. > > That's not entirely true. > > When you call (++), it does O(1) work. If you evaluate k cons cells. > it takes O(min(k,n)) work. I think we can safely simplify that to O(k) (at least for sequential programs). _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@... http://www.haskell.org/mailman/listinfo/haskell-cafe |
|
|
|
| Free Forum Powered by Nabble | Forum Help |