[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Map unionWith generalization

Subject: Re: [Haskell-cafe] Map unionWith generalization
From: Jan-Willem Maessen
Date: Wed, 27 Jan 2010 15:29:13 -0500
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

<Prev in Thread] Current Thread [Next in Thread>