Bringing the IntMap API up to par with the Map API

[Johan Tibell]

On Fri, Aug 6, 2010 at 5:00 PM, Milan Straka <fox at ucw.cz> wrote:

> Hi,
>
> > 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.

Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100806/f53775c0/attachment-0001.html