Monoids and Semigroups: Combining Things
The pilgrimage's epilogue promised more peaks — Monoids among them. This closes that loop: the single algebraic pattern behind addition, list concatenation, and string-joining, precise enough that GHC can check it, and general enough that it quietly powers half the standard library's folding functions.
The pattern hiding behind “combine these”
Numbers add. Lists concatenate. Strings join. Sets union. These all look like completely different operations — until you notice they share an identical shape: take two things of the same type, combine them, get back one more thing of that type. Haskell has a name for exactly this shape:
class Semigroup a where
(<>) :: a -> a -> a
(<>) (pronounced “mappend,” or often just “diamond”) is the combining operation, and the class comes with exactly one law, stated but not checked by the type system: associativity.
Figure: Associativity is the whole point — <> never needs a fixed grouping to give a well-defined answer, which is exactly what lets a list of values be combined in parallel, or in any chunking at all, and still get the identical result.
[1,2] <> ([3] <> [4,5]) and ([1,2] <> [3]) <> [4,5] both give [1,2,3,4,5] — parenthesization simply doesn’t matter. That might look like a small, obvious fact, but it’s the entire reason Semigroup is worth naming: a genuinely associative combining operation can be applied in any order, chunked any way, even computed in parallel across many machines and combined afterward — with a guarantee, not a hope, that the final answer is identical either way.
Monoid: a Semigroup with a starting point
Most of the operations above have something else in common too: an element that changes nothing when combined with anything else. 0 for addition, [] for list concatenation, "" for strings. A Semigroup with such an element is a Monoid:
class Semigroup a => Monoid a where
mempty :: a
-- law: mempty <> x = x = x <> mempty
instance Semigroup [a] where
(<>) = (++)
instance Monoid [a] where
mempty = []
mempty is the identity — combining it with anything leaves that thing unchanged, in either position. That single extra element turns out to be exactly what’s needed to fold an entire list of monoidal values down to one, with a well-defined answer even for an empty list:
mconcat :: Monoid a => [a] -> a
mconcat = foldr (<>) mempty
ghci> mconcat [[1,2], [3], [4,5]]
[1,2,3,4,5]
ghci> mconcat ([] :: [[Int]])
[]
Without mempty, mconcat [] would have no sensible answer to return — foldr (<>) mempty is only total because there’s always a value to fall back on, even for zero inputs.
Int has two perfectly good monoids — addition (identity 0) and multiplication (identity 1) — and Haskell only allows one instance of a class per type. Data.Monoid resolves the clash with two small newtype wrappers, Sum and Product, each picking one monoid explicitly:
newtype Sum a = Sum { getSum :: a }
instance Num a => Semigroup (Sum a) where
Sum x <> Sum y = Sum (x + y)
instance Num a => Monoid (Sum a) where
mempty = Sum 0
ghci> getSum (mconcat (map Sum [1,2,3,4]))
10
Whenever a type has more than one equally valid combining operation, a newtype wrapper — exactly Base Camp’s zero-cost trick — is how Haskell picks one without losing the other.
The deeper unification: foldMap
Foldable (the typeclass behind sum, length, and toList) has a method that quietly generalizes all of them at once:
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
ghci> foldMap Sum [1,2,3,4]
Sum {getSum = 10}
ghci> foldMap (\x -> [x,x]) [1,2,3]
[1,1,2,2,3,3]
foldMap maps every element into some monoid, then combines the results with <> — sum is foldMap Sum with the wrapper peeled off, string concatenation of a list of names is foldMap id, and even length is secretly foldMap (const (Sum 1)). One function, one law-abiding typeclass, and an enormous swath of “reduce a structure to one value” collapses into a single pattern.
Applicative (Chapter 10) is, underneath, a lax monoidal functor — the “monoidal” isn’t a coincidence of naming. pure () plays the role of mempty, and <*>’s job of combining two independent effectful computations plays the role of <>, just one level up: instead of combining two values, Applicative combines two computations that produce values, with the same associativity guarantee underneath. Monoids are the algebraic skeleton; Applicative is that skeleton wearing a functor.
Monoids show up constantly outside toy examples: build systems and CI pipelines combine independent test results with a Monoid instance (Passed <> Passed = Passed, anything else propagates a failure); metrics libraries combine counters and histograms collected on different threads with <>, relying on associativity to make the combination order-independent; and Data.Map’s own Semigroup instance (Common Algorithms) lets two maps be merged directly with <>, using each value’s own Semigroup instance to resolve overlapping keys automatically.
The pilgrimage’s own epilogue named Monoids as one of the further peaks only pointed toward. This is that peak, properly climbed: a two-line typeclass, one law, and — via foldMap — most of Foldable’s vocabulary turns out to be one idea wearing many names.