Bringing the IntMap API up to par with the Map API
wren ng thornton
wren at community.haskell.org
Wed Aug 18 21:41:29 EDT 2010
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
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.
More information about the Libraries