How can I merge 2 maps in Haskell

Question

If I have 2 Haskell Maps, for example:

[("a",1),
 ("b",2),
 ("c",1)]

and

[("a",1)]

How can I write a function in such a way that it would give something like:

[("a",2),("b",2),("c",1)]

Until now I could only write the base cases but that was all.

Answer 1

How about unionWith from Data.Map?

Here's a sample GHCi session using it on two maps m1 and m2 both containing the key 'a':

Prelude> import qualified Data.Map as Map
Prelude Data.Map> let m1 = Map.fromList [('a', 1)]
Prelude Data.Map> let m2 = Map.fromList [('a', 2), ('b', 10)]
Prelude Data.Map> Map.unionWith (+) m1 m2
fromList [('a',3),('b',10)]

---

If you want to define your own function to wrap all that up:

mergeMap :: (Ord k, Num a) => Map.Map k a -> Map.Map k a -> Map.Map k a
mergeMap = Map.unionWith (+)

which is the same as

mergeMap a b = Map.unionWith (+) a b

or even

a `mergeMap` b = Map.unionWith (+) a b

---

Note: in real life, make sure to make the right choice between lazy and strict maps, and hence between Data.Map.Strict.unionWith and Data.Map.Lazy.unionWith.

Answer 2

An alternative to Map is sort. This version assumes each key occurs only once in each list. If that's not the case, you could fix it up, but the Map approach would start looking a lot more attractive.

combine op xs ys = cs op (s xs) (s ys)
  where
    s = sortBy (compare `on` fst)

    cs _ [] qs = qs
    cs _ ps [] = ps
    cs op pss@(p@(pk,pv):ps) qss@(q@(qk,qv):qs) =
      case compare pk qk of
        LT -> p : cs op ps qss
        GT -> q : cs op pss qs
        EQ -> (pk, pv `op` qv) : cs op ps qs