doc request: runtime cost for Data.Map.differenceWith (and merge)
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
I'm just curious: why does `Data.Map.differenceWith` use `merge`, and where is its cost analysis?
(`difference` is as in the Blelloch et al. paper, but `merge` is not in there?)
If I'm not mistaken, the trivial implementation of `difference(With f) a b` is
* if a is small, then iterate over a (check whether x from a is in b, build new tree from the survivors): cost is size a * log (size b)
* if b is small, then iterate over b (delete each y in b from a): cost is size b * log (size a)
This looks like the general bound from the paper. m+n can be worse (if m is small-oh of n).
To me it seems (experimentally) that `differenceWith` is only very slightly more expensive than `difference`, and `difference large small` cost as much as `union large small`, while `difference small large` costs as much as `intersection small large` (for the case that the keys of `small` are thinly spread out in `large`)
So this is really only a doc request, as the actual behaviour seems fine - and better than the advertised bounds.
Contributor guide
Assessment
This issue has not been assessed yet.