Bringing the IntMap API up to par with the Map API

Milan Straka fox at ucw.cz
Fri Aug 6 11:00:09 EDT 2010


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.

Milan


More information about the Libraries mailing list