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