[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Map unionWith generalization

Subject: Re: [Haskell-cafe] Map unionWith generalization
From: Hans Aberg
Date: Wed, 27 Jan 2010 15:42:04 +0100
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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

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