Proposal: more general unionWith for Data.Map

[Milan Straka]

Hi,

> merge :: (a -> b -> Maybe c) -> (a -> Maybe c) -> (b -> Maybe c) ->
> Map k a -> Map k b -> Map k c
> mergeWithKey :: (k -> a -> b -> Maybe c) -> (k -> a -> Maybe c) ->
> (k-> b -> Maybe c) -> Map k a -> Map k b -> Map k c
> 
> where the function arguments are
> what to use when the key appears in both maps
> what to use when the key appears in just the left map
> what to use when the key appears in just the right map.
> 
> It seems like it would be the ultimate fully general fast map merging routine.
> 
> intersection = merge (Just . const) (const Nothing) (const Nothing)
> union = merge (Just . const) Just Just
> xor = merge ( const Nothing . const) Just Just
> 
> and so forth...

I agree with the ultimate generality, but the problem is efficiency. For
example running
  intersection (fromList [1..1000]) (fromList [1001..2000])
will end very soon with empty result, but
  merge (Just . const) (const Nothing) (const Nothing) (fromList [1..1000]) (fromList [1001..2000])
will call the (const Nothing) for 2000 times.

Cheers,
Milan