Proposal: containers: add indexing operations for Set

[Milan Straka]

> OK, that seems like a reasonable use case.
> 
> The existing documentation is lacking, though.  For example, the above
> use case requires that: 0 <= index < Map.size map

Yes, that is the case. The documentation should definitely improve.

> It's also not specified that the index refers to the index in the
> sorted sequence.  Of course, that problem here is that "Ord" -- which
> is really an implementation detail -- becomes part of the specified
> properties of a Map/Set. E.g., the same function for HashMap probably
> wouldn't make that guarantee.

Agreed. These indexing methods work only for OrderededSet and
OrderedMap, not for HashMap and HashSet.

If the Data.Set and Data.Map modules were called Data.OrdSet
and Data.OrdMap, then there would be no problem including the indexing
API in them. Personally I consider Data.Set to be Data.OrdSet, not
a generic Set API. If we every create a Set class, the indexing API will
definitely _not_ be part of it.

BTW, the indexing API is currently _not_ part of IntSet and IntMap. The
reason is that the data structure does not allow efficient
implementation of the indexing API.

> I.e., what are the properties of these functions?  Do we have:
> 
>   - findIndex a set `compare` findIndex b set ==> a `compare` b

it is even true that

 - findIndex a set `compare` findIndex b set <==> a `compare` b

because (flip findIndex set) is a bijection respecting ordering.

>   - findIndex a set == findIndex a (Set.toList set)

This one holds too. It could be considered a definition of
Set.findIndex, but the Set.findIndex is more efficient than
the list version.

Cheers,
Milan