haskell / haskell/containers

doc request: runtime cost for Data.Map.differenceWith (and merge)

Open
#566 3 comments 0 reactions 0 assignees View on GitHub
docs Map
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

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.