[Haskell-cafe] Map unionWith generalization

[Jan-Willem Maessen]

On Jan 27, 2010, at 5:53 AM, Hans Aberg wrote:

> I need ideally some generalizations of unionWith and unionWithKey, for efficiency matters (i.e. avoiding conversions and traversing the maps more than once). I could use a modification of the code in Map.hs, but then the problem is that the module Map interface does not export the constructors of data Map. So suggestions are welcome.
> 
> For example, in Map String Integer (sparse representation of monomials) compute the minimum value of all associative pairs with the same key (the gcd); if only one key is present, the absent should be treated as having value 0. So
>  unionWith min xs ys
> will not work, because unionWith will always apply the identity to the remaining value when one key is missing, whereas it should be sent to 0.
> 
> So here, one would want:
>  (a -> c) -> (b -> c) -> (a -> b -> c) -> Map k a -> Map k b -> Map k c
> where the two first functions are applied when the first or second key is missing.

Ah, the swiss army knife function on maps.  This particular formulation works well for the application you describe above, where you're completely traversing both maps.  The following really grubby variant can be used to implement asymptotically efficient variations of union, intersection, difference, etc., etc:

swissArmy ::
  (Map k a -> Map k c) ->    -- Used to process submaps unique to the left map
  (Map k b -> Map k c) ->    -- Used to process submaps unique to the right map
  (a -> b -> Maybe c) ->     -- Used to process a single common entry
  Map k a -> Map k b -> Map k c

Then your function appears to be:

-- helper
just2 :: (a -> b -> c) -> a -> b -> Maybe c
just2 f a b = Just (f a b)

swissArmy (fmap (const 0)) (fmap (const 0)) (just2 gcd)

Here are unionWith and intersectionWith:

unionWith f = swissArmy id id (just2 f)
intersectionWith = swissArmy (const empty) (const empty) (just2 f)
differenceWith = swissArmy id (const empty) (\a b -> Nothing)

When throwing together tree-like data structures, I often start by writing this function; it handles most of the bulk operations I might want to do as one-liners.  It's got a messy, ugly type signature, but it does everything you want as efficiently as you want.*

-Jan-Willem Maessen

* Actually, this is only true if you add the key as an argument to the third function, so that you can also encode unionWithKey etc!  I've skipped that here.