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
>>> But it is a good idea to have a Maybe so that one can remove keys on the
>> A good point. Technically, one should delimit the scope of the first two
>> 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
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
>> 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
>> 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.
Haskell-Cafe mailing list