[Haskell-cafe] Map unionWith generalization

[Hans Aberg]

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