Hans Aberg haberg at math.su.se
Wed Jan 27 09:42:04 EST 2010

```On 27 Jan 2010, at 14:56, Jan-Willem Maessen wrote:

>> 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

I'm not sure why you want to throw in functions between maps in the
two first arguments. Then there is no requirement that single keys are
preserved.

But it is a good idea to have a Maybe so that one can remove keys on
the fly.

> 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.*

My guess is that is when you write things from scratch.

I wanted to add these function on top of the module Data.Map, but then
that seems not to be possible, as the constructors are not exported. I
could make a copy of this file, and then make my own variation.

Hans

```