Hans Aberg haberg at math.su.se
Wed Jan 27 16:17:37 EST 2010

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

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

```