Can I rewrite this unionWith-like function with Applicative instead Monad?

Question

I tried to write a function similar to Data.Map.unionWith, but may fail. The original one uses Maybe, which indeed is a Monad, so the monadic one just works fine for me. but I wonder if it can be rewritten with Applicative, since I fmapped it with pure just to satisfy the type requirement of unionWith. Or with other function in Data.Map instead of unionWith?

{-# LANGUAGE RankNTypes #-}
import Control.Monad
import Data.Map
unionWithM :: (Monad m, Traversable t)
          => (forall a. (a -> a -> a)
              -> t a
              -> t a
              -> t a
             )
          -> (v -> v -> m v)
          -> t v
          -> t v
          -> m (t v)
unionWithM u f a b = sequenceA (u f' (pure <$> a) (pure <$> b))
  where f' x y = join $ f <$> x <*> y

unionWithOriginal :: Ord k => (a -> a -> Maybe a) -> Map k a -> Map k a -> Maybe (Map k a)
unionWithOriginal f a b = sequenceA (unionWith f' (Just <$> a) (Just <$> b))
  where f' x y = join $ f <$> x <*> y

Answer 1

Yes you can but you need an intermediate data structure. The problem is you wrap the value of your Map before applying the function, which is why your f' is of type m a -> m a -> m a. To transform f to f' you need join, i.e. a Monad. The trick is to apply the function after the union. For that you could use (Maybe a, Maybe a) which is a bit messy, so instead you can use the These data type. If we roll it out manually you get

data These a b = That a | This b | These a b

unionWith' f a b = let theses = unionWith These (That <$> a) (This <$> b)
                   in sequenceA (f' <$> theses)
    where f' (That a) = pure a
          f' (This b) = pure b
          f' (These a b) = f a b

If you use the these package you can simplify it to

 unionWith'' f a b = sequenceA $ alignWith (these pure pure f)  a b