<div class="gmail_quote">On Fri, Aug 6, 2010 at 5:00 PM, Milan Straka <span dir="ltr"><<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi,<br>
<div class="im"><br>
> There are a few functions on Maps that could be implemented on IntMaps but<br>
> aren't:<br>
><br>
> - deleteAt<br>
> - elemAt<br>
> - updateAt<br>
> - findIndex<br>
> - lookupIndex<br>
><br>
> The above 5 functions can be efficiently implemented on Maps in O(log n)<br>
> time, as the size of the subtrees are known, but not not on IntMaps. We<br>
> could still provide O(n) versions for IntMap. What's the use case for<br>
> indexed lookup in maps? I've never seen it in other languages.<br>
<br>
</div>Or there is the other alternative -- to drop these functions from<br>
Data.Map. These functions are usually not available in other languages<br>
and the implementation is essentially forced to store the size of the<br>
subtrees in the tree. That is convenient for Adams' balanced trees, but<br>
not for AVL trees, red-black trees, tries (IntMap) etc.</blockquote><div><br></div><div>If we could show that no one uses them (i.e. by surveying Hackage) we could remove them.</div><div><br></div><div>Johan</div><div> </div>
</div>