[Haskell-cafe] Map unionWith generalization

[Jan-Willem Maessen]

On Jan 27, 2010, at 10:54 AM, Hans Aberg wrote:

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

That has the same behavior semantically, but it's no more efficient than performing a unionWith followed by a filter.  For example, consider implementing:

xs `intersection` singleton k v

in this way.  With the function given, the complexity is necessarily O(size xs): we must traverse every key/value pair in xs.  By contrast, by aggregating the operations on keys that exist only in a single map, we can write functions like intersection with the desired complexity (which is O(log (size xs)) in this case).

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

Traversing cross products is a very different operation from zipping in the key space.  Again I wouldn't want to mistakenly substitute one for the other!  But in this case I think you'll find that you're already well served by the functions that already exist---adding this function doesn't enable you to do anything more efficiently (at least in a big-O sense).

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

Understood, and with a sufficiently smart compiler we might analyze the behavior of the function and do the right thing with the single-function interface in both cases.  I have yet to encounter a compiler that is both smart and reliable on this count.  That is why I've found it necessary to expose these kinds of functions.

-Jan

> 
>  Hans
> 
>