Bringing the IntMap API up to par with the Map API

[wren ng thornton]

Johan Tibell wrote:
> I've created a proposal to add a strict left fold, see separate email. In
> the process of doing so I've discovered that the whole foo/fooWithKey
> duplication is unnecessary, at least from a performance perspective.
> [...]
> It's probably not feasible to remove the duplication from e.g. the Data.Map
> API, but it's worth keeping in mind when designing data structure APIs in
> the future.

For API designers, note that this is not true for all "map like" 
structures. As a specific example, trie structures often have much 
slower *WithKey variants because they have to reconstruct the keys. I 
forget how much slower my benchmarks were for Data.Trie, but it was 
certainly significant. Even with inlining and the like I didn't have any 
luck getting the overhead to automatically fall away when the key isn't 
used.

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'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.

-- 
Live well,
~wren