On Thu, Aug 19, 2010 at 3:41 AM, wren ng thornton <span dir="ltr">&lt;<a href="mailto:wren@community.haskell.org">wren@community.haskell.org</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Johan Tibell wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
I&#39;ve created a proposal to add a strict left fold, see separate email. In<br>
the process of doing so I&#39;ve discovered that the whole foo/fooWithKey<br>
duplication is unnecessary, at least from a performance perspective.<br></div>
[...]<div class="im"><br>
It&#39;s probably not feasible to remove the duplication from e.g. the Data.Map<br>
API, but it&#39;s worth keeping in mind when designing data structure APIs in<br>
the future.<br>
</div></blockquote>
<br>
For something like Data.Map, the API is definitely redundant (though we may wish to keep the simplified versions around in Data.Map.Convenience or the like). And even though Data.IntMap is technically a trie, it&#39;d probably be fine without them too--- since the keys are of fixed size, and can be combined with bit twiddling instead of rearranging memory.<br>

</blockquote><div><br></div><div>The keys are actually stored in the leaves in the IntMap keys so what I said about Map applies to IntMap as well.</div><div><br></div><div>-- Johan </div></div>