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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe