[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 10:33:13 -0500
On Jan 27, 2010, at 9:42 AM, Hans Aberg wrote:

> On 27 Jan 2010, at 14:56, Jan-Willem Maessen wrote:
> 
>>> So here, one would want:
>>> (a -> c) -> (b -> c) -> (a -> b -> c) -> Map k a -> Map k b -> Map k c
>>> where the two first functions are applied when the first or second key is 
>>> missing.
>> 
>> Ah, the swiss army knife function on maps.  This particular formulation 
>> works well for the application you describe above, where you're completely 
>> traversing both maps.  The following really grubby variant can be used to 
>> implement asymptotically efficient variations of union, intersection, 
>> difference, etc., etc:
>> 
>> swissArmy ::
>> (Map k a -> Map k c) ->    -- Used to process submaps unique to the left map
>> (Map k b -> Map k c) ->    -- Used to process submaps unique to the right map
>> (a -> b -> Maybe c) ->     -- Used to process a single common entry
>> Map k a -> Map k b -> Map k c
> 
> 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

>> When throwing together tree-like data structures, I often start by writing 
>> this function; it handles most of the bulk operations I might want to do as 
>> one-liners.  It's got a messy, ugly type signature, but it does everything 
>> you want as efficiently as you want.*
> 
> My guess is that is when you write things from scratch.

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.

I bet there's even a fusion framework in here somewhere.

-Jan_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

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