Proposal: add Int indexing functions to Data.Set

[Luis Casillas]

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Data-Set.hs.patch
Type: application/octet-stream
Size: 4739 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110428/1e4a20c6/attachment.obj>