Module documentation for 0.0.4.3

• Data
  • Data.MonoidMap

monoidmap

Overview

This library provides aMonoidMap type that:

• models atotal function withfinite support from keys tomonoidal values, with a default value ofmempty.
• encodes key-value mappings with aminimal encoding that onlyincludes valuesnot equal tomempty.
• provides a comprehensive set ofmonoidal operations for transforming, combining, and comparing maps.
• provides ageneral basis for building more specialised monoidal data structures.

Relationship between keys and values

A map of type MonoidMap k v associatesevery possible key of typek with a value of typev:

MonoidMap.get :: (Ord k, Monoid v) => k -> MonoidMap k v -> v

Theempty map associates every keyk with a default value ofmempty:

∀ k. MonoidMap.get k MonoidMap.empty == mempty

Comparison with standardMap type

TheMonoidMap type differs from the standardcontainersMap type in how it relates keys to values:

This difference can be illustrated by comparing the type signatures of operations to query a key for its value, for both types:

      Map.lookup ::             k ->       Map k v -> Maybe vMonoidMap.get    :: Monoid v => k -> MonoidMap k v ->       v

Whereas a standardMap has a default value ofNothing, aMonoidMap has a default value ofmempty:

∀ k.       Map.lookup k       Map.empty == Nothing∀ k. MonoidMap.get    k MonoidMap.empty == mempty

In practice, the standardMap type usesMaybe to indicate thepresence orabsence of a value for a particular key. This representation is necessary because theMap type imposes no constraints on value types.

However,monoidal types already have a natural way to represent null or empty values: themempty constant, which represents the neutral or identity element of aMonoid.

Consequently, using a standardMap with amonoidal value type gives rise totwo distinct representations for null or empty values:

In contrast, theMonoidMap type provides a single,canonical representation for null or empty values, according to the following conceptual mapping:

Advantages of using a canonical representation

A canonical representation formempty values can make it easier to correctly implement operations that compare or combine pairs of maps.

When comparing or combining maps of the standardcontainersMap type, there aretwo cases to consider for each keyk in each map:

• Mapm associatesk withNothing.
• Mapm associatesk withJust v.

With apair of maps, there arefour possible cases to consider for each key.

For maps with monoidal values, and in contexts that assume or require a default value ofmempty, there are nowthree cases to consider for each map:

• Mapm associatesk withNothing.
• Mapm associatesk withJust v wherev == mempty.
• Mapm associatesk withJust v wherev /= mempty.

With apair of maps, there are nownine possible cases to consider for each key.

Mishandling cases such as these can give rise to subtle bugs that manifest in unexpected places. For maps with more complex value types (such as maps that nest other maps), the number of cases requiring consideration can easily multiply further, making it even easier to introduce bugs.

Since allMonoidMap operations provide a canonical representation formempty values, it’s possible to write functions that compare or combine maps without having to considerNothing and Just mempty as separate cases.

Encoding

AMonoidMap only encodes mappings from keys to values that arenot equal tomempty.

The total function $T$ modelled by aMonoidMap is encoded as asupport map $S$, where $S$ is the finite subset of key-value mappings in $T$ for which values arenot equal tomempty (denoted by $\varnothing$):

$S = \{ (k, v) \in T \ |\ v \ne \varnothing \} $

Automatic minimisation

AllMonoidMap operations performautomatic minimisation of the support map, so thatmempty values do not appear in:

• any encoding of aMonoidMap;
• any traversal of aMonoidMap.

Constraints on values

MonoidMap operations require the monoidal value type to be an instance ofMonoidNull.

Instances ofMonoidNull must provide anull indicator function that satisfies the following law:

null v == (v == mempty)

MonoidMap operations use thenull indicator function to detect and excludemempty values from the support map.

Note that it isnot generally necessary for the value type to be an instance ofEq.

The set of monoidal types that admit aMonoidNull instance is strictly larger than the set of monoidal types that admit anEq instance.

For any typev that is an instance of bothEq andMonoid, it isalways possible to define aMonoidNull instance:

instance MonoidNull v where    null = (== mempty)

However, there are monoidal types for which it is possible to define aMonoidNull instance, but not practical (or possible) to define a lawfulEq instance.

For example, consider the following type:

Maybe (String -> Sum Natural)

Requiring aMonoidNull constraint instead of anEq constraint allowsMonoidMap to be usable with a greater range of monoidal value types.

Examples of automatic minimisation

Consider the following operation, which constructs a map of typeMonoidMap Int String:

>>> m0 = fromList [(1, "hello"), (2, "brave"), (3, "new"), (4, "world")]>>> m0fromList [(1, "hello"), (2, "brave"), (3, "new"), (4, "world")]

TheMonoid instance forString definesmempty to be the emptyString"".

If we update the map to associate key3 with value"", that association will no longer appear when encoding the map:

>>> m1 = MonoidMap.set 3 "" m0>>> m1fromList [(1, "hello"), (2, "brave"), (4, "world")]

However, we can still read the updated value for key3:

>>> MonoidMap.get 3 m1""

Consider the following operation, which constructs a map of typeMonoidMap Char (Sum Natural):

>>> m = fromList [('a', Sum 0), ('b', Sum 1), ('c', Sum 2), ('d', Sum 3)]

TheMonoid instance for Sum Natural definesmempty to beSum 0.

The original list contained a mapping from key'a' to valueSum 0, but that association will not appear when encoding the map:

>>> mfromList [('b', Sum 1), ('c', Sum 2), ('d', Sum 3)]

Nevertheless, we can still read the value for key'a':

>>> MonoidMap.get 'a' mSum 0

Consider the following operations, which construct two maps of typeMonoidMap Char (Sum Natural):

>>> m1 = fromList [('a', Sum 1), ('b', Sum   1 )]>>> m2 = fromList [('a', Sum 1), ('b', Sum (-1))]

TheSemigroup instance for Sum Natural defines<> as equivalent to ordinary addition.

If we add both maps together with<>, then each key in the resulting map will be associated with the result of applying<> to each matching pair of values in the original maps. However, adding together the values for key'b' with<> producesSum 0, so this value will not appear in the encoding:

>>> m1 <> m2fromList [('a', Sum 2)]

Nevertheless, we can still read the value for key'b':

>>> MonoidMap.get 'b' (m1 <> m2)Sum 0

Advantages of automatic minimisation

Consistency

Automatic exclusion ofmempty values can help to ensure consistency when encoding to or decoding from other formats such as JSON, CBOR, or YAML.

For example, you may wish to ensure that:

• Whenencoding a map, nomempty values appear in the encoded result.
• Whendecoding a map, nomempty values appear in the decoded result.

Performance

Automatic exclusion ofmempty values makes it possible to perform certain operations inconstant time, rather than in linear time, as it is never necessary to traverse the entire map in order to determine which values may or may not bemempty:

Memory usage

Automatic minimisation makes it easier to reason about the memory usage of aMonoidMap, as memory is not required to encode mappings from keys to empty values.

This is a useful property for large, long-lived map structures that are subject to multiple updates over their lifetimes, where it’s important to not retain large numbers of mappings from keys to empty values.

Simplicity

Some total map data types only perform minimisation whenexplicitly demanded to.

For example, theTMap data type provides atrim operation that traverses the map and removes any values that are equal to thedefault value. This approach has some advantages, such the ability to provide a lawfulFunctor instance.

However, this approach also has some disadvantages:

• It might not be obviouswhen it’s necessary to calltrim. For example, consider the following operation:m1 <> m2. Could this operation produce a map where some keys map to default values? (Answer: it depends on the choice of default value and the underlying value type.)
• Callingtrim when itisn’t necessary might adversely affect performance, sincetrim must traverse the entire data structure.
• Not callingtrim when itis necessary might affect correctness. The compiler will not help here, as trimmed and untrimmed maps share the same type.
• Even iftrim is a semantic no-op, default values canstill be made visible by operations that encode maps to other types.

Since allMonoidMap operations perform automatic minimisation when appropriate, it’s not necessary for users to reason about when or whether it’s necessary to “trim” the map.

Furthermore, for nested maps such as MonoidMap k1 (MonoidMap k2 v), automatic minimisation of inner maps enables seamless automatic minimisation of outer maps. See theNestedMonoidMap type for an example of this.

Limitations of automatic minimisation

TheMonoidMap type has noFunctor instance, as the requirement to excludemempty values means that themap operation must removemempty values from its result. Therefore,map doesnot unconditionally satisfy the functor composition law:

map (f . g) == map f . map g

Consider the followingMonoidMapm:

m :: MonoidMap String Stringm = singleton "k" "v"

And the following functionsf andg:

f :: a -> Stringf = const "z"g :: Monoid a => b -> ag = const mempty

By substituting the above definitions into the left-hand side of the functor composition law, we obtain:

map (f . g) m = map (const "z" . const mempty) (singleton "k" "v")              = map (const "z"               ) (singleton "k" "v")              =                                (singleton "k" "z")

By substituting the above definitions into the right-hand side of the functor composition law, we obtain:

map f (map g m) = map (const "z") (map (const mempty) (singleton "k" "v"))                = map (const "z") mempty                =                 mempty

This leads to the following inequality between the left-hand side and right-hand side:

singleton "k" "z" /= mempty

Therefore, for this example, the functor composition law is not satisfied.

However, if applying functionf tomempty producesmempty, the functor composition law is satisfied:

(f mempty == mempty) ==> (∀ g. map (f . g) == map f . map g)

Monoidal operations

TheMonoidMap type provides a comprehensive set of monoidal operations for transforming, combining, and comparing maps.

Instances for severalsubclasses ofSemigroup andMonoid are provided, including classes from the following libraries:

• monoid-subclasses
• groups

At the root of this hierarchy of subclasses is theSemigroup class, whose instance forMonoidMap is defined in terms of theunderlying value type, so that applying<> to apair of maps is equivalent to applying<> to allpairs of values for matching keys:

∀ k. MonoidMap.get k (m1 <> m2) == MonoidMap.get k m1 <> get k m2

In general, operations for subclasses ofSemigroup andMonoid are definedanalogously to theSemigroup instance, so that:

• unary operations onindividual maps are defined in terms of their distributive application to all values.
• binary operations onpairs of maps are defined in terms of their distributive application to allpairs of values for matching keys.

Unary monoidal operations typically satisfy a property similar to:

∀ k. MonoidMap.get k (f m) == f (MonoidMap.get k m)

Binary monoidal operations typically satisfy a property similar to:

∀ k. MonoidMap.get k (f m1 m2) == f (MonoidMap.get k m1) (MonoidMap.get k m2)

Defining monoidal operations in this way makes it possible to transform, combine, and compare maps in ways that are consistent with the algebraic properties of the underlying monoidal value type.

Examples of monoidal operations and their properties

Examples of monoidal operations applied to values

For maps withSet-based values,MonoidMap.union andMonoidMap.intersection compute theSet.union andSet.intersection of each pair of matching values, respectively.

Consider the following maps of typeMonoidMap Char (Set Integer):

>>> m1 = fromList [('a', Set.fromList [0, 1]), ('b', Set.fromList [3, 4])]>>> m2 = fromList [('a', Set.fromList [0, 2]), ('b', Set.fromList [3, 5])]

TheMonoidMap.union of mapsm1 andm2 is a map that associates every keyk with theSet.union of the corresponding sets fork inm1 andm2:

>>> m1 `union` m2fromList [('a', Set.fromList [0,1,2]), ('b', Set.fromList [3,4,5])]

TheMonoidMap.intersection of mapsm1 andm2 is a map that associates every keyk with theSet.intersection of the corresponding sets fork inm1 andm2:

>>> m1 `intersection` m2fromList [('a', Set.fromList [0]), ('b', Set.fromList [3])]

Consider the following maps of typeMonoidMap Char (Sum Integer):

>>> m1 = fromList [('a', Sum 10), ('b', Sum 20), ('c, Sum 40)]>>> m2 = fromList [('a', Sum 40), ('b', Sum 20), ('c, Sum 10)]

TheMonoidMap.invert operation produces a new map where every key is associated with the negation of its value in the original map:

>>> invert m1fromList [('a', Sum (-10)), ('b', Sum (-20)), ('c, Sum (-40))]>>> invert m2fromList [('a', Sum (-40)), ('b', Sum (-20)), ('c, Sum (-10))]

TheMonoidMap.minus operation, when applied to mapsm1 andm2, produces a new map where every keyk is associated with the value ofk inm1 minus the value ofk inm2:

>>> m1 `minus` m2fromList [('a', Sum (-30)), ('c', Sum 30)]>>> m2 `minus` m1fromList [('a', Sum 30), ('c', Sum (-30))]

For maps with Sum Natural values,MonoidMap.union andMonoidMap.intersection compute themaximum andminimum of each pair of matching values, respectively:

>>> m1 = fromList [('a', Sum 10), ('b', Sum 20)]>>> m2 = fromList [('a', Sum 20), ('b', Sum 10)]>>> m1 `union` m2fromList [('a', Sum 20), ('b', Sum 20)]>>> m1 `intersection` m2fromList [('a', Sum 10), ('b', Sum 10)]

For maps with Product Natural values,MonoidMap.union andMonoidMap.intersection compute thelowest common multiple (LCM) andgreatest common divisor (GCD) of each pair of matching values, respectively:

>>> m1 = fromList [('a', Product  6), ('b', Product 15), ('c', Product 35)]>>> m2 = fromList [('a', Product 15), ('b', Product 35), ('c', Product 77)]>>> m1 `union` m2fromList [('a', Product 30), ('b', Product 105), ('c', Product 385)]>>> m1 `intersection` m2fromList [('a', Product 3), ('b', Product 5), ('c', Product 7)]

General basis for more specialised map types

TheMonoidMap type can be used as a general basis for building other more specialised map types.

If you have aMap-based data type with an invariant that valuesmust not bemempty, then by expressing this type in terms ofMonoidMap,MonoidMap will handle the invariant for you:

- newtype SomeMap k v = SomeMap (      Map k (SomeMonoidalContainer v))+ newtype SomeMap k v = SomeMap (MonoidMap k (SomeMonoidalContainer v))

If you’re already using a specialised non-empty container type to enforce the invariant that values must not be empty, thenMonoidMap makes it possible toreplace the use of the specialised non-empty container type with its ordinary equivalent:

Example transformations:

  -- Non-empty lists:- newtype ListMap k v = ListMap (      Map k (NonEmpty v))+ newtype ListMap k v = ListMap (MonoidMap k          [v])  -- Non-empty sets:- newtype SetMap k v = SetMap (      Map k (NonEmptySet v))+ newtype SetMap k v = SetMap (MonoidMap k         (Set v))  -- Non-empty sequences:- newtype SeqMap k v = SeqMap (      Map k (NonEmptySeq v))+ newtype SeqMap k v = SeqMap (MonoidMap k         (Seq v))

UsingMonoidMap can simplify the implementation of such types, as special handling code for empty values can often be greatly simplified or even eliminated.

Real-world examples from the Haskell ecosystem

Example:SignedMultiSet (a signed multiset type)

Thesigned-multiset library provides theSignedMultiSet type, which is internally defined as aMap from elements to signed integer occurrence counts:

newtype SignedMultiset a = SMS {unSMS :: Map a Int}

AllSignedMultiSet operations maintain an invariant that the internalMapmust not contain any mappings to0 (zero). This requiresSignedMultiSet functions to detect and eliminate values of0.

For example, theinsertMany operation:

insertMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset ainsertMany x n = SMS . Map.alter f x . unSMS  where    f Nothing  = Just n    f (Just m) = let k = m + n in if k == 0 then Nothing else Just k

Let’s redefineSignedMultiSet in terms ofMonoidMap:

- newtype SignedMultiset a = SMS {unSMS ::       Map a      Int }+ newtype SignedMultiset a = SMS {unSMS :: MonoidMap a (Sum Int)}

Here we’ve used theSum wrapper type, whoseMonoid instance definesmempty asSum 0, and<> as ordinary addition.

Now we can redefineinsertMany (and similar operations) in a simpler way:

  insertMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a+ insertMany x n = SMS . MonoidMap.adjust (+ Sum n) x . unSMS- insertMany x n = SMS . Map.alter f x . unSMS-   where-     f Nothing  = Just n-     f (Just m) = let k = m + n in if k == 0 then Nothing else Just k

Since theMonoidMap.adjust operation performs automatic minimisation, values ofSum 0 are automatically excluded from the internal data structure, and there is no need to handle them differently from non-zero values.

Example:SetMultiMap (a set-based multimap type)

Themulti-containers library provides theSetMultiMap type, which is internally defined as aMap from keys to (possibly-empty) sets of values, together with aSize parameter that records the total number of elements in the map (counting duplicates):

newtype SetMultimap k a = SetMultimap (Map k (Set a), Size)type Size = Int

AllSetMultiMap operations maintain an invariant that the internalMapmust not contain any mappings to empty sets. This requiresSetMultiMap functions to detect and eliminate values ofSet.empty (indicated by theSet.null function).

For example, thealterWithKey operation detects if the updated set is empty, and if so, performs a deletion instead of an insertion:

alterWithKey :: Ord k => (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k aalterWithKey f k mm@(SetMultimap (m, _))    | Set.null as = fromMap (Map.delete k    m)    | otherwise   = fromMap (Map.insert k as m)  where    as = f k (mm ! k)fromMap :: Map k (Set a) -> SetMultimap k afromMap m = SetMultimap (m', sum (fmap Set.size m'))  where    m' = Map.filter (not . Set.null) m

Let’s redefineSetMultiMap in terms ofMonoidMap:

- newtype SetMultimap k a = SetMultimap (      Map k (Set a), Size)+ newtype SetMultimap k a = SetMultimap (MonoidMap k (Set a), Size)

Now we can provide a simpler definition foralterWithKey (and other operations):

alterWithKey :: Ord k => (k -> Set a -> Set a) -> k -> SetMultimap k a -> SetMultimap k aalterWithKey f k (SetMultimap (m, size)) = SetMultiMap    (MonoidMap.set k new m, size - Set.size old + Set.size new)  where    old = MonoidMap.get k m    new = f k old

Since theMonoidMap.set operation performs automatic minimisation, empty sets are automatically excluded from the internal data structure, and there is no need to handle them any differently from non-empty sets.

Example:MultiMap (a list-based multimap type)

Themulti-containers library provides theMultiMap type, which is internally defined as aMap from keys to non-empty lists of values, together with aSize parameter that records the total number of elements in the map (counting duplicates):

newtype Multimap k a = Multimap (Map k (NonEmpty a), Size)type Size = Int

AllMultiMap operations maintain the invariant that the internalMapmust not contain any mappings to empty lists. This invariant is handled rather nicely by the use of theNonEmpty list type, which disallows empty listsby construction. As a result, it’s arguably more difficult to make a mistake in the implementation than it would be ifMultiMap were defined in terms of ordinary lists.

However, certain operations still need to differentiate between the empty and non-empty case, and it’s still necessary to handle each case specially.

For example, thealterWithKey operation detects if the updated list is empty, and if so, performs a deletion instead of an insertion:

alterWithKey :: Ord k => (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k aalterWithKey f k mm@(Multimap (m, _)) = case nonEmpty (f k (mm ! k)) of    Just as' -> fromMap (Map.insert k as' m)    Nothing  -> fromMap (Map.delete k     m)fromMap :: Map k (NonEmpty a) -> Multimap k afromMap m = Multimap (m, sum (fmap length m))

Let’s redefineMultiMap in terms ofMonoidMap and ordinary lists:

- newtype Multimap k a = Multimap (      Map k (NonEmpty a), Size)+ newtype Multimap k a = Multimap (MonoidMap k          [a], Size)

Now we can provide a simpler definition foralterWithKey (and other operations):

alterWithKey :: Ord k => (k -> [a] -> [a]) -> k -> Multimap k a -> Multimap k aalterWithKey f k (Multimap (m, size)) = MultiMap    (MonoidMap.set k new m, size - List.length old + List.length new)  where    old = MonoidMap.get k m    new = f k old

Since theMonoidMap.set operation performs automatic minimisation:

• empty lists are automatically excluded from the internal data structure.
• there is no need to use a specialisedNonEmpty type.
• there is no need to handle empty lists differently from non-empty lists.

Example:MultiAsset (a nested map type)

Thecardano-ledger library provides theMultiAsset type, which models anested mapping fromPolicyID keys toAssetName keys toInteger values:

newtype MultiAsset c = MultiAsset (Map (PolicyID c) (Map AssetName Integer))

EachInteger value represents the value of anasset on the Cardano blockchain, where each asset is uniquely identified by the combination of aPolicyID and anAssetName. (Multiple assets can share the samePolicyID.)

AllMultiAsset operations maintain adual invariant that:

• there must be no mappings fromPolicyID keys to empty maps; and that
• there must be no mappings fromAssetName keys toInteger values of0.

To satisfy this invariant,MultiAsset operations use a variety of helper functions to ensure thatMultiAsset values are always in a canonical form.

For example, consider theSemigroup instance forMultiAsset:

instance Semigroup (MultiAsset c) where    MultiAsset m1 <> MultiAsset m2 =        MultiAsset (canonicalMapUnion (canonicalMapUnion (+)) m1 m2)

The above definition of<> performs pointwise addition of all pairs of values for matching assets.

For example, if:

• MultiAssetm1 maps asseta to a value of10;
• MultiAssetm2 maps asseta to a value of20;

Then:

• MultiAssetm1 <> m2 will map asseta to a value of30.

The definition of<> uses a function calledcanonicalMapUnion, which does the heavy lifting work of performing a union while ensuring that each resultingMap is in canonical form.

Let’s have a look at the definition ofcanonicalMapUnion:

canonicalMapUnion ::  (Ord k, CanonicalZero a) =>  (a -> a -> a) ->  Map k a ->  Map k a ->  Map k acanonicalMapUnion _f t1 Tip                 = t1canonicalMapUnion  f t1 (Bin _ k x Tip Tip) = canonicalInsert f k x t1canonicalMapUnion  f (Bin _ k x Tip Tip) t2 = canonicalInsert f k x t2canonicalMapUnion _f Tip t2                 = t2canonicalMapUnion  f (Bin _ k1 x1 l1 r1) t2 = case Map.splitLookup k1 t2 of  (l2, mb, r2) -> case mb of    Nothing ->      if x1 == zeroC        then link2 l1l2 r1r2        else link k1 x1 l1l2 r1r2    Just x2 ->      if new == zeroC        then link2 l1l2 r1r2        else link k1 new l1l2 r1r2      where        new = f x1 x2    where      !l1l2 = canonicalMapUnion f l1 l2      !r1r2 = canonicalMapUnion f r1 r2

ThecanonicalMapUnion function in turn relies oncanonicalInsert, which handles individual insertions:

canonicalInsert ::  (Ord k, CanonicalZero a) =>  (a -> a -> a) ->  k ->  a ->  Map k a ->  Map k acanonicalInsert f !kx x = go  where    go Tip = if x == zeroC then Tip else Map.singleton kx x    go (Bin sy ky y l r) =      case compare kx ky of        LT -> link ky y (go l) r        GT -> link ky y l (go r)        EQ -> if new == zeroC then link2 l r else Bin sy kx new l r          where            new = f y x

Similarly, theinsertMultiAsset function, which “inserts” the value of an individual asset into aMultiAsset value, has the following definition:

insertMultiAsset ::  (Integer -> Integer -> Integer) ->  PolicyID c ->  AssetName ->  Integer ->  MultiAsset c ->  MultiAsset cinsertMultiAsset combine pid aid new (MultiAsset m1) =  case Map.splitLookup pid m1 of    (l1, Just m2, l2) ->      case Map.splitLookup aid m2 of        (v1, Just old, v2) ->          if n == 0            then              let m3 = link2 v1 v2               in if Map.null m3                    then MultiAsset (link2 l1 l2)                    else MultiAsset (link pid m3 l1 l2)            else MultiAsset (link pid (link aid n v1 v2) l1 l2)          where            n = combine old new        (_, Nothing, _) ->          MultiAsset            ( link                pid                ( if new == 0                    then m2                    else Map.insert aid new m2                )                l1                l2            )    (l1, Nothing, l2) ->      MultiAsset        ( if new == 0            then link2 l1 l2            else link pid (Map.singleton aid new) l1 l2        )

A notable feature of all the above functions is that they completely eschew the use ofMap.merge. Instead, they directly manipulate constructors exported fromMap.Internal. This approach was probably taken for performance reasons.

However, it’s clear that maintaining the invariant in this way comes at acost: the code is rather complex, and it were not for a comprehensive test suite, it would probably be very easy to introduce a regression.

In the spirit of demonstration, let’s see what happens if we redefine theMultiAsset type in terms ofMonoidMap:

- newtype MultiAsset c = MultiAsset (Map       (PolicyID c) (      Map AssetName      Integer))+ newtype MultiAsset c = MultiAsset (MonoidMap (PolicyID c) (MonoidMap AssetName (Sum Integer))

Note that we have replacedInteger with Sum Integer, whoseMonoid instance definesmempty as Sum 0, and whoseSemigroup instance defines<> as equivalent to ordinary integer addition.

Recall that allMonoidMap operations automatically take care of the invariant that values cannot bemempty. For theMultiAsset type, this means that:

• outer maps are now prevented from including any mappings fromPolicyID to empty inner maps.
• inner maps are now prevented from including any mappings fromAssetName to values of Sum 0.

As a result, we can remove virtually all code that deals with canonicalisation.

For example, we can now simplify theSemigroup instance forMultiAsset, dispensing entirely with the need to callcanonicalMapUnion:

  instance Semigroup (MultiAsset c) where      MultiAsset m1 <> MultiAsset m2 =-         MultiAsset (canonicalMapUnion (canonicalMapUnion (+)) m1 m2)+         m1 <> m2

Given that the above instance is trivial, we can even derive theSemigroup andMonoid instances automatically:

  newtype MultiAsset c = MultiAsset (MonoidMap (PolicyID c) (MonoidMap AssetName (Sum Integer))+     deriving newtype (Semigroup, Monoid)

We can also simplify theinsertMultiAsset function:

  insertMultiAsset ::    (Integer -> Integer -> Integer) ->    PolicyID c ->    AssetName ->    Integer ->    MultiAsset c ->    MultiAsset c  insertMultiAsset combine pid aid new (MultiAsset m1) =+   MultiAsset $+   MonoidMap.adjust+     (MonoidMap.adjust (\(M.Sum old) -> M.Sum (combine old new)) aid) pid m1-  ...-  ### 27 lines deleted ###-  ...

Finally, sinceMonoidMap already providesEq andGroup instances that are defined in terms of the underlying monoidal value type, we can automatically deriveEq andGroup instances forMultiAsset:

  newtype MultiAsset c = MultiAsset (MonoidMap (PolicyID c) (MonoidMap AssetName (Sum Integer))-     deriving newtype (Semigroup, Monoid)+     deriving newtype (Eq, Semigroup, Monoid, Group)- instance Eq (MultiAsset c) where-   MultiAsset x == MultiAsset y = pointWise (pointWise (==)) x y-- instance Group (MultiAsset c) where-   invert (MultiAsset m) =-     MultiAsset (canonicalMap (canonicalMap ((-1 :: Integer) *)) m)

Many other simplifications are also possible. (Left as an exercise for readers!)

Comparison with other generalised map types

The Haskell ecosystem has several different types for maps with monoidal properties, and several different types that model total functions from keys to values. Each type comes with its own set of advantages and limitations.

Here’s a comparison between theMonoidMap type provided by this library and types provided by other libraries:

0.0.4.3

• Moved all modules frommonoidmap-internal to main library.

0.0.4.2

• Removed the dependency onnonempty-containers.

0.0.4.1

• Fixed spelling error in documentation.
• Added the haddocknot-home marker toData.MonoidMap.Internal.

0.0.4.0

• Added thefromMapWith function toMonoidMap.

0.0.3.0

• Added themapWithKey function toMonoidMap.

0.0.2.1

• Added support for GHC 9.12.

0.0.2.0

• Added thefromSet function toMonoidMap.

0.0.1.9

• Added the following traversal functions toMonoidMap:
  • traverse
  • traverseWithKey
  • mapAccumL
  • mapAccumLWithKey
  • mapAccumR
  • mapAccumRWithKey

0.0.1.8

• Added strict variant of thefoldMapWithKey function.

0.0.1.7

• Added a selection of folding operations forMonoidMap.

0.0.1.6

• Updated version bounds for dependencies.

0.0.1.5

• Updated version bounds for dependencies.

0.0.1.4

• Added support for GHC 9.10.

0.0.1.3

• Updated version bounds for dependencies.

0.0.1.2

• Updated version bounds for dependencies.

0.0.1.1

• Updated version bounds for dependencies.

0.0.1.0

• Added support for GHC 9.8.
• Optimised performance ofSemigroup.stimes operation forMonoidMap.

0.0.0.1

• RevisedMultiMap examples and documentation.

0.0.0.0

• Initial release.