Re: Proposal: add Int indexing functions to Data.Set

However, indexing precludes the use of implementations that *don't*

cache subtree sizes on a large fraction of interior node

The Data.Map API also precludes hash-map implementations, should we then remove 90% of the functionality because of that?

I'd support removing these functions absent a compelling use case (ie one that would not be better expressed as indexing by key). Does anyone have one?

Does splitting at the middle for parallel processing qualify as a compelling use case? (though for that purpose maybe it would be better to expose splitting the tree structure, since it is balanced anyway, and also unsafely joining two trees). My experience with the Map/Set API is that there are lots of use cases one doesn't think of in advance. Balazs On Fri, Apr 29, 2011 at 5:05 PM, Jan-Willem Maessen wrote:

...

On 29 April 2011 15:33, Luis Casillas wrote:

...

El abr 28, 2011, a las 9:16 p.m., Ivan Lazar Miljenovic escribió:

...

On 29 April 2011 14:08, Luis Casillas wrote:

...

2. Concern that Int-based indexing breaks the set abstraction by

exposing a specific ordering (Trac comment by Malcolm Wallace). My assumption when I decided to submit this patch was that if it's OK for Data.Map to have these operations, then it should also be ok for Data.Set to have them. But Malcolm's concern makes me wonder if some people will find

...

...

...

I think I agree with Malcolm here; the internals of Data.Set shouldn't be revealed IMHO.

Would either of the following modifications make the proposal more

On Fri, Apr 29, 2011 at 1:42 AM, Ivan Lazar Miljenovic wrote: the original Data.Map functions objectionable and dislike the idea of "spreading the infection" to Data.Set. palatable?

...

...

1. Stressing in the functions' documentation that the assignment of Ints

does not have to reflect the order of the elements. The examples would also be rewritten not to make any ordering assumptions.

...

2. Modifying the implementation to scramble the order of the indexes

relative to the order of the set elements. This would discourage people from implicitly coding to the element order.

...

...

Well, before we talk about modifications, etc.: is there a _need_ for this kind of indexing in a Set?

I believe there is not. Moreover, in order to realize efficient Int indexing, we need to commit a word of storage to hold subtree size on every interior tree node in Data.Map, Data.Set, Data.IntSet, and Data.IntMap. Without extra interior storage, these tree indexing and list indexing are comparably slow (O(n)).

My understanding is these functions were included in Data.Map *because we could*: the implementation uses size-balanced trees, so the tree size had to be kept at each node for balancing purposes, and therefore it was easy to implement indexing. As a happy side effect, this also makes it easy to maintain O(1) size information.

However, indexing precludes the use of implementations that *don't* cache subtree sizes on a large fraction of interior nodes (it is already a bad match for IntSet and IntMap). There are other techniques for making size O(1) without imposing per-node overhead, if that is desired. It would be a shame to rule out alternative implementations in order to support an API that nobody needs.

I'd support removing these functions absent a compelling use case (ie one that would not be better expressed as indexing by key). Does anyone have one?

-Jan-Willem Maessen

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries