Proposal: containers: add indexing operations for Set

[Milan Straka]

> > I'd like to add the following indexing operations for Data.Set.Set, to
> > complement the existing functions for Data.Map.Map:
> >
> > findIndex :: Ord a => a -> Set a -> Int
> > lookupIndex :: Ord a => a -> Set a -> Maybe Int
> > elemAt :: Int -> Set a -> a
> > deleteAt :: Int -> Set a -> Set a
> 
> I'm surprised that these functions already exists in Data.Map.  What
> are the use cases?

For an ordered Set, it makes sense to be able to work with the elements
using their ordering -- i.e., to work with "i-th least element of s",
i.e. the element toAscList s !! i.

If you have for example a set of words of some language, you might want
to work with those not explicitly, but using "i-th word of the language".

Of you might want to find the median of the elements in the set.

> I assume the only sensible semantics is to behave as a slightly more
> efficient version of the same function working on "Set.toList set"
> which must be ordered.

Yes. But the "slightly" means exponentially -- getting the median of the
set takes linear time using Set.toList, but only logarithmic time using
Set.elemAt.

> I don't think that breaks any abstractions, but they do seem like very
> weird functions to have.  Something that I might consider potentially
> useful function would be a variant of splitAt, so that you could split
> a set using a fixed ratio (e.g., "splitAt (Set.size set `div` 2) set").

splitAt index set = split (elemAt index set) set

would work reasonably well. It traverses the tree twice, but the first
traversal is very fast.

Cheers,
Milan