Proposal: containers: add indexing operations for Set
Milan Straka
fox at ucw.cz
Wed Jul 4 20:04:43 CEST 2012
> > 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
More information about the Libraries
mailing list