[Haskell-cafe] Map unionWith generalization

[Jan-Willem Maessen]

On Jan 27, 2010, at 9:42 AM, Hans Aberg wrote:

> 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.

A good point.  Technically, one should delimit the scope of the first two arguments:

data KeyPreservingMapOperation k a b = AlwaysEmpty | Identity | MapMaybeWithKey (k -> a -> Maybe b)

perform :: KeyPreservingMapOperation a b -> Map k a -> Map k b
perform AlwaysEmpty = const empty
perform Identity = id
perform (MapMaybeWithKey f) = mapMaybeWithKey f

>> 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.

Yes.  On the other hand, I've repeatedly run into the same problem you're describing: a api that doesn't give me an efficient way to perform an operation I know to be very simple.  If every map provided an operation like this one, then I can avoid writing my own library "from scratch" when I need it --- especially when "from scratch" means "fork the code and add what I need".

So, library implementors: think hard about your "swiss army knife" combinators.  You end up with messy functions with gigantic signatures.  On the other hand, you can often add a couple of judicious INLINE annotations and remove tons of code from the rest of your library.  Then expose them, and mark them as the functions of last resort that they truly are.

I bet there's even a fusion framework in here somewhere.

-Jan