Proposal: add Int indexing functions to Data.Set

[wren ng thornton]

On 4/29/11 12:30 PM, Luis Casillas wrote:
> I think this really distills the issue down to this.  There is a family of three potential, related abstractions:
>
>                           plain set
>                             /   \
>                            /     \
>                  ordered set     indexed set
>
> A plain set just provides uniqueness.  An ordered set provides uniqueness and preserves some ordering predicate on the elements.  An indexed set assigns a unique Int index in the range [0..size-1] to each element, and provides translation between members and indexes.
>
> The Set module provides an implementation of an efficient ordered set, that can easily be extended to also be an indexed set.  But many people think that "plain set" should be the only contract that Data.Set is bound to implement.  I can't say that I disagree with that--but I also just want indexed sets...

So why not just implement your "set" with a map from elements to their 
indices? Maps maintain uniqueness of keys, and Data.Map maintains 
ordering too. It wouldn't be as clean as the proposed functions, but 
from your description of the problem, it's not clear to me that using 
sets of proxies for array indices is really the cleanest approach in the 
first place.

-- 
Live well,
~wren