Bringing the IntMap API up to par with the Map API
johan.tibell at gmail.com
Fri Aug 6 13:07:32 EDT 2010
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
> > 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Libraries