
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 treelike data structures, I often start by writing this
function; it handles most of the bulk operations I might want to do as
oneliners. It's got a messy, ugly type signature, but it does everything you
want as efficiently as you want.*
JanWillem 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.
_______________________________________________
HaskellCafe mailing list
HaskellCafe@xxxxxxxxxxx
http://www.haskell.org/mailman/listinfo/haskellcafe

