Add general merge API

[treeowl]

Data.Map and Data.IntMap offer merge and mergeA operations that can take unions, intersections, differences, etc. We should be able to do something quite similar here. I suspect optimal merge will have to be a bit different from mergeA rather than just a specialization, thanks to the way arrays work. Also, as I've explored in a slightly different context, mergeA can probably be implemented particularly efficiently for certain transformer stacks on top of IO or ST s, again thanks to the mutable array business. Dunno if that sort of thing is worth bothering with.

[sjakobi]

This addition would help us address the feature requests #240 and #242.

I guess implementing merge and testing it against the Data.Map version would be a good first step!?

[sjakobi]

This should be the right type, no?

merge :: (Hashable k, Eq k)
             => SimpleWhenMissing k a c -- ^ What to do with keys in @m1@ but not @m2@
             -> SimpleWhenMissing k b c -- ^ What to do with keys in @m2@ but not @m1@
             -> SimpleWhenMatched k a b c -- ^ What to do with keys in both @m1@ and @m2@
             -> HashMap k a
             -> HashMap k b
             -> HashMap k c

Could the merge strategies ([Simple]WhenMissing etc) simply be copied from http://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Map-Merge-Lazy.html?

[treeowl]

That's the general idea. You'll probably want to look at the Data.IntMap version too. The hard part is figuring out how mergeA should work. The rest is much easier.

[sjakobi]

@BebeSparkelSparkel would you possibly be interested in working on this?

[BebeSparkelSparkel]

I am concerned about the the performance of foldr (merge f0 f1 f2) mempty (see below) in my use case #240 . It looks like it would create a lot of maps during the fold, but maybe I'm wrong about that.

[sjakobi]

@BebeSparkelSparkel Note that unions is also simply defined as foldl' union empty.

Do you have a more efficient implementation in mind?

[treeowl]

I doubt a much more generally efficient implementation of unions is possible. It'll either be foldl' union empty or foldr' union empty, depending on the Foldable.

[BebeSparkelSparkel]

I was mistaken. foldr (merge f0 f1 f2) mempty is incorrect. What I actually need is more like fmap f0 . foldr (merge f1 f2 f3) mempty if using merge.

#240 details Foldable f => (NonEmpty a -> b) -> f (HashMap k a) -> HashMap k b has the merge and map while only creating the resulting HashMap.

It seems to me like #226 and #240 are not addressing the same problem.

[sjakobi]

I think I'll give merge a spin myself. It looks like a nice exercise for me to better understand the internals.