Proposal: add Int indexing functions to Data.Set

Edward Kmett ekmett at gmail.com
Mon May 2 23:14:24 CEST 2011


On Fri, Apr 29, 2011 at 10:44 AM, Antoine Latter <aslatter at gmail.com> wrote:

> 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.
>
>
IntMap and IntSet do not provide efficient size operations -- they have very
different asymptotics than Map and Set in this regard, O(n) vs O(1). This
makes the requested operations quite uselessly expensive there.

While I don't like the existence of the Int indexed Map operations in the
first place, I'm hardly swayed by an argument that boils down to claiming
that because nobody seems to want to port them to a largely unrelated but
unsuitable data structure, we shouldn't implement them on another data
structure where they _can_ be efficiently implemented.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110502/3292f2f5/attachment.htm>


More information about the Libraries mailing list