Using monadic functions with Data.Map (fx unionWith)

Question

I would like to union two Map instances with a monadic function. This becomes a problem because of the unionWith type signature:

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

I'm looking for a smart way to do this. Here is my naive implementation:

monadicUnionWith :: (Monad m, Ord k) => (a -> a -> m a) -> Map k a -> Map k a -> m (Map k a)
monadicUnionWith f mapA mapB = do
  let overlapping = toList $ intersectionWith (\a b -> (a,b)) mapA mapB
  mergedOverlapping <- liftM fromList $ mapM helper overlapping
  return $ union (union mergedOverlapping mapA) mapB
  where
    helper (k, (a,b)) = do
      c <- f a b
      return (k, c)

Note that union is left biased

Your code doesn’t look too bad ;-)

Joachim Breitner
– Joachim Breitner

2013-11-10 22:51:46 +00:00
Commented Nov 10, 2013 at 22:51 — Joachim Breitner
– Joachim Breitner, Commented Nov 10, 2013 at 22:51

Joachim Breitner · Accepted Answer · 2013-11-10 23:05:19Z

7

Not sure if it is more efficient, but it is somewhat cooler (as it involves storing monadic values in the map):

monadicUnionWith :: (Monad m, Ord k) => (a -> a -> m a) -> Map k a -> Map k a -> m (Map k a)
monadicUnionWith f mapA mapB =
  Data.Traversable.sequence $ unionWith (\a b -> do {x <- a; y <- b; f x y}) (map return mapA) (map return mapB)

And if you want you can use

(\a b -> join (liftM2 f a b))

as the parameter to unionWith, or even

((join.).(liftM2 f))

edited Nov 10, 2013 at 23:05

answered Nov 10, 2013 at 22:55

Joachim Breitner

25.9k7 gold badges83 silver badges149 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Joachim Breitner Over a year ago

Hmm, it probably is more efficient, as the tree structure of the map is not destroyed (as with fromList and toList).

RasmusWL Over a year ago

Yes, that was why I called my own solution "stupid". It didn't keep the tree structure. I should have just looked up how mapM was implemented, but didn't think of that then.

John J. Camilleri Over a year ago

It should be noted that the map function used here is from Data.Map, not Prelude.

Collectives™ on Stack Overflow

Using monadic functions with Data.Map (fx unionWith)

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related