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

[jwaldmann]

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.

[treeowl]

The bound you give is looser than that of Blelloch et al. You're right that we could implement differenceWith the trivial way you suggest and get a simple and reasonably decent bound. However, I believe that what we currently do is almost certainly more efficient. On the other hand, no one has proven that what we currently do for differenceWith is as good as the trivial implementation! Without such a proof, we can't claim such a bound. Since differenceWith is a strange function, no one has attempted the proof. You're certainly welcome to try. If you could even prove the looser bound you suggest, that would certainly be an improvement.

[treeowl]

As for why differenceWith uses merge, my bet is that someone came up with the idea for mergeWithKey and implemented differenceWith to demonstrate its utility. When I came up with the safer merge interface, I reimplemented differenceWith using that. You might learn more by digging through the revision history.

[jwaldmann]

Is there any published cost analysis for merge? is O(n+m) obvious?

It'd be a nice showcase for automated (runtime/derivationa) complexity analysis, e.g., using methods of https://link.springer.com/chapter/10.1007%2F978-3-540-78969-7_11