[Haskell-cafe] Map unionWith generalization

[Hans Aberg]

On 27 Jan 2010, at 16:33, Jan-Willem Maessen wrote:

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

I'm thinking about
   (k -> Maybe a -> Maybe b -> Maybe c) -> Map k a -> Map k b -> Map k c
The first two Maybe's tell if the keys are present, the last if one  
wants it in the resulting map.

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

One can transverse the product of keys. Then I'm thinking about
   (k1 -> k2 -> a -> b -> Maybe c -> Maybe(k, c)) -> Map k1 a -> Map  
k2 b -> Map k c
The first Maybe tells if the key is already present; the second if one  
wants it inserted.

The idea in both cases is to combine the modifying functions into one.  
This simplifies the interface.

   Hans