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 >>> preserved. >>> >>> But it is a good idea to have a Maybe so that one can remove keys on the >>> fly. >> >> A good point. Technically, one should delimit the scope of the first two >> arguments: >> >> 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 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). >> 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 >> need". >> >> 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. -Jan > > Hans > > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
