Add generalization of Data.Map.unionWith with (a -> b -> c) as the combining function

[joeyadams]

The signature of  Data.Map.unionWith is:

unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a

 intersectionWith, on the other hand, has a more general signature:

intersectionWith :: Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c

The reason the combining function in unionWith is constrained to (a -> a -> a) is because of the possibility of values in one map not present in the other. unionWith only applies the combining function for values present in both maps; it uses existing values for the rest.

I'd like to be able to write this function:

-- | Combine two maps.  Substitute 'Nothing' for any value present in only one
-- of the maps.
unionMaybes :: Ord k => Map k a -> Map k b -> Map k (Maybe a, Maybe b)

However, it's awkward with unionWith:

unionMaybes left right =
        Map.unionWith combine (Map.map mkLeft left) (Map.map mkRight right)
    where
        mkLeft   l = (Just l, Nothing)
        mkRight  r = (Nothing, Just r)
        combine (Just l, Nothing) (Nothing, Just r) = (Just l, Just r)
        combine _ _ = error "Shouldn't happen"

It'd be nicer to have a generalization of unionWith that can transform values only present in one of the maps. Here is such a function, implemented in terms of unionWith:

-- | Like 'Map.unionWith', but apply a function even when a key is present in
-- only one of the maps.
--
-- @'Map.unionWith' = 'combine' 'id' 'id'@
combine :: Ord k
        => (a -> c)         -- ^ For keys only present in the left map
        -> (b -> c)         -- ^ For keys only present in the right map
        -> (a -> b -> c)    -- ^ For keys present in both maps
        -> Map k a          -- ^ Left map
        -> Map k b          -- ^ Right map
        -> Map k c
combine onLeft onRight onBoth left right =
        Map.map apply $
        Map.unionWith combine_ (Map.map LeftOnly left) (Map.map RightOnly right)
    where
        combine_ (LeftOnly l) (RightOnly r) = LeftRight l r
        combine_ _ _ =
            error "combine: internal error (Data.Map.unionWith is not combining values correctly)"

        apply (LeftOnly l)    = onLeft l
        apply (RightOnly r)   = onRight r
        apply (LeftRight l r) = onBoth l r

data Combine l r = LeftOnly l
                 | RightOnly r
                 | LeftRight l r

This way, unionMaybes can be written as:

unionMaybes :: Ord k => Map k a -> Map k b -> Map k (Maybe a, Maybe b)
unionMaybes = combine (\l   -> (Just l,  Nothing))
                      (\r   -> (Nothing, Just r))
                      (\l r -> (Just l,  Just r))

[tibbe]

containers upstream is not maintained by GHC HQ anymore. The main repo and bug tracker is at  https://github.com/haskell/containers

As for this proposal, you'll be happy to hear that a similar proposal was accepted recently (see discussion on the libraries list) and we'll be adding generalized merge operations. Milan Straka is responsible for merging the changes. He's been a bit busy lately but we'll get to it.