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