haskell / haskell/containers

mergeWithKey' may be too general for its own good

Open
#227 0 comments 0 reactions 0 assignees View on GitHub
IntMap performance
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

It's cute that `mergeWithKey'` can implement so many different things, but there's a performance cost. Different operations necessitate different `Nil` checking, which `mergeWithKey'` has no way to deal with. The fact that the functions passed to it are often partial is also a bit disturbing, suggesting there may be a better approach. Having the combining function take maps instead of keys and values to enhance sharing sounds very reasonable until you see that it's actually only called for `Tip` trees. So the sharing is probably significant, but not earth-shattering. Using something like the evil pointer equality check could potentially have a much bigger impact, I imagine. Short of that, the partial functions could be avoided by passing both the `Tip` and its contents in separate arguments, although that's kind of ugly.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.