[Haskell-cafe] Map unionWith generalization

[Hans Aberg]

On 27 Jan 2010, at 21:29, Jan-Willem Maessen wrote:

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

It would not be the complexity, but the constant factor, by not having  
to transverse it twice. I'm not sure how it works in a functional  
language, and the trees must be rebalanced, too.

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

That is a good point.

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

For the first one, think of sums of sparse matrices or polynomials,  
and the second, products.

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

Yes, I can't implements (-) directly; it must be a combination of (+)  
and negate, and the 0 must be filtered out in an extra pass. And for  
gcd of monomials, it is now a combination of lcm, (*) and (/), instead  
of a single pass. Unfortunately, these operations are used a lot, so  
getting a smaller constant factor is important.

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

By your example above, there may be a conflict between a general,  
simple interface, and implementing things like intersections.

   Hans