Most idiomatic way to merge a map

Learn
#1

This is my first question in this forum. I am looking for an idiomatic way to implement the merger of multiple Tributes instances into a single one. In the example below, Rome wants to know how many units of gold and wine its two provinces Greece and Egypt owe it in January and February.

data Tribute = Gold | Wine
    deriving (Show, Eq)

type City = String

type Tributes = Map City (Map Tribute Integer)

january :: Tributes
january = Map.fromList
    [ ("Abydos", Map.fromList [(Gold, 7)])
    , ("Rhodes", Map.fromList [(Gold, 6), (Wine 11)])
    ]

february :: Tributes
february = Map.fromList
    [ ("Athens", Map.fromList [(Gold, 8), (Wine 4)])
    , ("Abydos", Map.fromList [(Gold, 5), (Wine 9)])
    ]

Rome doesn’t know enough Haskell to implement merging the two months but it expects the following result:

januaryAndFebruary = Map.fromList
     [ ("Abydos", Map.fromList [(Gold, 12), (Wine 9)])
     , ("Rhodes", Map.fromList [(Gold, 6), (Wine 11)])
     , ("Athens", Map.fromList [(Gold, 8), (Wine 4)])
     ]

Of course Octavian knows that he could define a function like merge :: Tributes -> Tributes -> Tributes and work his way through the details with some guiding examples and a good set of tests. But he wonders if there might be a better way to do this.

2 Likes
#2

You can do it using Map.unionWith twice:

ghci> Map.unionWith (Map.unionWith (+)) january february 
fromList
  [ ( "Abydos" , fromList [ ( Gold , 12 ) , ( Wine , 9 ) ] )
  , ( "Athens" , fromList [ ( Gold , 8 ) , ( Wine , 4 ) ] )
  , ( "Rhodes" , fromList [ ( Gold , 6 ) , ( Wine , 11 ) ] )
  ]
3 Likes
#3

It would be more idiomatic to use the (<>) semigroup append function, but the Semigroup instance for Map is bad (it will just overwrite values of duplicate keys instead of combining them). There is an alternative package called monoidal-containers which provides better Semigroup and Monoid instances for Map, but that does not change other functions such as fromList, which also behave badly. Unfortunately, this will probably not get fixed soon because of backwards compatibility concerns. I am considering creating a better-monoidal-containers package which doesn’t care about backwards compatibility.

4 Likes
#4

Thank you! I was more thinking of a solution with <> like you mention in the comment below. In Plutus.V1.Ledger.Value they seem to implement it for Value. But Map.unionWith is more than fine and suits perfectly. This really helped.

1 Like