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.
I've also considered Map and Set to be OrdMap and OrdSet for quite a while. If we ever add a type class to abstract over e.g. HashMap and Map we'd probably call it Data.Map.Class or something.
A potential downside to adding these functions is that I don't know if we can support them efficiently with a different implementation of ordered trees than the size-balanced ones. I still think we should add them though.
Any balanced tree can support indexing API, as long as every subtree stores its size. That is obviously trivially true for size-balanced trees, as the subtree sizes are used for balancing. If for example AVL trees were used, sizes would have to be stored explicitly in every node for indexing API to work fast. The complexity of 'size' also depends on whether sizes are stored explicitly in every node -- Data.Map.size is constant-time operation. Consider IntMap -- there sizes are not stored in the nodes, so we have no indexing API and 'size' is linear-time operation. BTW, when I last benchmarked it, adding size to every node of a red-black tree increased the time complexity of insert, lookup and delete by 0-5%. Nevertheless, I also think we should add indexing API to Data.Set. Cheers, Milan