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