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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
