Proposal: add Int indexing functions to Data.Set

[Antoine Latter]

On Thu, Apr 28, 2011 at 11:08 PM, Luis Casillas <luis at casillas.org> wrote:
> Hi everybody.  First time proposer here, so bear with me.
>
> While I was looking at the Haddock documentation for Data.Map, I noticed that it has a section with "Indexed" operations that address the map with Int indexes:
>
> http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map.html#g:19
>
> The relevant functions' signatures are these:
>
> lookupIndex :: Ord k => k -> Map k a -> Maybe Int
> findIndex :: Ord k => k -> Map k a -> Int
> elemAt :: Int -> Map k a -> (k, a)
> updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
> deleteAt :: Int -> Map k a -> Map k a
>
> Now, the Data.Set module, which is a near carbon-copy of Data.Map, does not have any counterparts to these functions.  My proposal is to add such counterparts to Data.Set (I'm writing some code that could benefit from them).  The proposed functions' signatures:
>
> lookupIndex :: Ord a => a -> Set a -> Maybe Int
> findIndex :: Ord a => a -> Set a -> Int
> elemAt :: Int -> Set a -> a
> deleteAt :: Int -> Set a -> Set a
>
> I attach a patch to add these to Data.Set.  Note that the implementation of the Set functions is basically a copy-paste-and-edit of their counterparts in Data.Map.  That seems to be the convention in those two modules; Data.Set is really just like Data.Map but with no "value" field in the datatype's constructor.
>
> Since I am a noob, I mistakenly created a Trac ticket before figuring out the correct library proposal process (#5162, which promptly got closed; my apologies).  There have been a couple of responses there, which I will summarize here:
>
> 1. Concern over the efficiency of the code in my patch (Trac comment by tibbe).  At my present skill level with Haskell, frankly, the most intelligent response I can give to this is that I'm copying the Data.Map implementation from darcs to the best of my ability, and that the most I hope is to make the Set versions no worse than the Map versions.
>
> 2. Concern that Int-based indexing breaks the set abstraction by exposing a specific ordering (Trac comment by Malcolm Wallace).  My assumption when I decided to submit this patch was that if it's OK for Data.Map to have these operations, then it should also be ok for Data.Set to have them.  But Malcolm's concern makes me wonder if some people will find the original Data.Map functions objectionable and dislike the idea of "spreading the infection" to Data.Set.
>
> Discussion period: 2 weeks.
>

These functions are also missing from IntSet and IntMap.

Assuming that there is a use case for such a family of indexing
functions, it seems like they should be added to these as well.

However if we don't have folks that want to use these functions for
sets or IntMaps, I don't think we should add them.

It's hard for me to imagine the Data.Map indexing functions making any
code clearer - are there cases where they can improve the performance
of complex updates?

Antoine