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