Bringing the IntMap API up to par with the Map API

[kahl at cas.mcmaster.ca]

Johan Tibell <johan.tibell at gmail.com> wrote:
 > 
 > On Fri, Aug 6, 2010 at 5:00 PM, Milan Straka <fox at ucw.cz> wrote:
 >
 > > > There are a few functions on Maps that could be implemented on IntMaps
 > > but
 > > > aren't:
 > > >
 > > >   - deleteAt
 > > >   - elemAt
 > > >   - updateAt
 > > >   - findIndex
 > > >   - lookupIndex
 > > >
 > > > The above 5 functions can be efficiently implemented on Maps in O(log n)
 > > > time, as the size of the subtrees are known, but not not on IntMaps. We
 > > > could still provide O(n) versions for IntMap. What's the use case for
 > > > indexed lookup in maps? I've never seen it in other languages.
 > >
 > > Or there is the other alternative -- to drop these functions from
 > > Data.Map. These functions are usually not available in other languages
 > > and the implementation is essentially forced to store the size of the
 > > subtrees in the tree. That is convenient for Adams' balanced trees, but
 > > not for AVL trees, red-black trees, tries (IntMap) etc.
 > 
 > 
 > If we could show that no one uses them (i.e. by surveying Hackage) we could
 > remove them.

I would consider it a feature of the current data structures
that they allow efficient implementations of the sub-interface
constituted by these functions.
Together with the efficiency characteristics of their other operations,
it makes these trees a useful alternative to lists and/or arrays
in certain circumstances.

For different data structures, it may make no difference whether they are
implemented inside or outside their defining modules,
but since Data.Map.Map etc. are exported as abstract datatypes,
these functions need to be defined inside and exported.


(And I have used them.)



Wolfram