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

On Fri, Apr 29, 2011 at 1:42 AM, Ivan Lazar Miljenovic 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 the original Data.Map functions objectionable and dislike the idea of "spreading the infection" to Data.Set.

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 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