[Haskell-cafe] Map unionWith generalization
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:
>> 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
More information about the Haskell-Cafe
mailing list