Re: Bringing the IntMap API up to par with the Map API

Johan Tibell wrote:

On Fri, Aug 6, 2010 at 5:00 PM, Milan Straka 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