[Top] [All Lists]

Re: [Haskell-cafe] Map unionWith generalization

Subject: Re: [Haskell-cafe] Map unionWith generalization
From: Jan-Willem Maessen
Date: Wed, 27 Jan 2010 08:56:42 -0500
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., 

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.

Haskell-Cafe mailing list

<Prev in Thread] Current Thread [Next in Thread>