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