Monoid

A monoid is a set with an associative binary operation and an identity element for it: the integers under addition with 0, strings under concatenation with the empty string, functions from a set to itself under composition with the identity function. Because the operation is associative, a sequence of elements can be combined with any bracketing, so a computation that combines many values in a monoid can be split into parts and done in parallel, incrementally or in a tree^[8]. Lists are the free monoid: any function from elements into a monoid extends in exactly one way to a function from lists that respects the operation. In functional programming, monoids underlie folds, the Foldable abstraction, the writer monad and the annotations of finger trees.

§ 01

Definition

A monoid is a set $M$ with a binary operation $⋄ : M \times M \to M$ and an element $e \in M$ such that, for all $a, b, c \in M$ :

(a ⋄ b) ⋄ c = a ⋄ (b ⋄ c) e ⋄ a = a = a ⋄ e

The first law is associativity and the second says that $e$ is a two-sided identity. The identity is unique: if $e$ and $e^{'}$ are both identities then $e = e ⋄ e^{'} = e^{'}$ . A set with an associative operation but no identity is a semigroup, and a monoid in which every element has an inverse is a group^[1]. A monoid is commutative if $a ⋄ b = b ⋄ a$ for all $a, b$ .

Because of associativity, the combination of a finite sequence $a_{1}, \dots, a_{n}$ does not depend on how it is bracketed, and it can be written without brackets as $a_{1} ⋄ \dots ⋄ a_{n}$ . The identity gives a value to the combination of the empty sequence, so every finite sequence has one:

concat [] = e concat [a_{1}, \dots, a_{n}] = a_{1} ⋄ \dots ⋄ a_{n}

§ 02

Examples

Numbers form monoids in several ways: $(Z, +, 0)$ , $(Z, \times, 1)$ , and the integers extended with $- \infty$ under $max$ . Booleans form monoids under conjunction with $true$ and disjunction with $false$ . Strings and lists form monoids under concatenation, which are not commutative. The functions from a set $X$ to itself form a monoid under composition, with the identity function; it is called the endomorphism monoid of $X$ . The product of two monoids is a monoid with the operation applied componentwise, and the functions from any set into a monoid form a monoid pointwise.

Monoids as OCaml modules, their product, a generic concat, and a randomized test of the laws.

module type MONOID = sig
  type t
  val empty : t
  val ( <+> ) : t -> t -> t
end
 
module Sum = struct type t = int let empty = 0 let ( <+> ) = ( + ) end
module Product = struct type t = int let empty = 1 let ( <+> ) = ( * ) end
module Max = struct type t = int let empty = min_int let ( <+> ) = max end
module All = struct type t = bool let empty = true let ( <+> ) = ( && ) end
module Str = struct type t = string let empty = "" let ( <+> ) = ( ^ ) end
 
(* Functions from a type to itself, under composition. *)
module Endo = struct type t = int -> int let empty = Fun.id let ( <+> ) f g x = f (g x) end
 
(* The product of two monoids is a monoid, componentwise. *)
module Pair (A : MONOID) (B : MONOID) = struct
  type t = A.t * B.t
  let empty = (A.empty, B.empty)
  let ( <+> ) (a, b) (a', b') = (A.( <+> ) a a', B.( <+> ) b b')
end
 
(* Combining a whole list needs only the two operations. *)
module Concat (M : MONOID) = struct let concat xs = List.fold_left M.( <+> ) M.empty xs end
 
(* The three laws, tested on random elements. *)
module Laws (M : MONOID) = struct
  let check gen =
    let ok = ref true in
    for _ = 1 to 10_000 do
      let a = gen () and b = gen () and c = gen () in
      let open M in
      if (a <+> b) <+> c <> (a <+> (b <+> c)) || empty <+> a <> a || a <+> empty <> a then ok := false
    done;
    !ok
end

Running it.

sum 31   product 6480   max 9
count 8, max 9, all below 10: true   (one pass, one monoid)
concat [(+1); ( * 2); (-3)] applied to 10 = 15
laws: Sum true, Max true, Str true

The product monoid computes several results in one traversal: the count, the maximum and a conjunction are combined into a single triple per element. Concatenating a list of functions in the endomorphism monoid composes them, so the rightmost is applied first. OCaml has no type classes, so a monoid is a module and code generic over monoids is a functor; in Haskell it is the Monoid class, with mempty and <>.

§ 03

Associativity and parallelism

A left fold brackets a sequence as $((a_{1} ⋄ a_{2}) ⋄ a_{3}) ⋄ \dots$ and must run sequentially. For a monoid the balanced bracketing $(a_{1} ⋄ a_{2}) ⋄ (a_{3} ⋄ a_{4})$ gives the same result, and its two halves are independent, so they can be computed on different processors and combined^[8]. With $p$ processors, $n$ elements are combined in $O (n / p + lo g p)$ time. Parallel reductions and prefix sums rely on this^[6], and so does MapReduce, whose reduce step must be associative for partial results to be combined in any order^[5].

A left fold and a balanced tree fold over the same array.

(* Associativity is what allows a fold to be split up: the list can be
   bracketed any way, so halves can be combined independently. *)
let rec fold_tree op empty = function
  | [||] -> empty
  | [| x |] -> x
  | a ->
      let n = Array.length a / 2 in
      op (fold_tree op empty (Array.sub a 0 n)) (fold_tree op empty (Array.sub a n (Array.length a - n)))

Running it.

int sum:    left fold 499500000   tree fold 499500000
float sum:  left fold 14.392726722864989
            tree fold 14.392726722865723
(0.1 +. 0.2) +. 0.3 = 0.60000000000000009
0.1 +. (0.2 +. 0.3) = 0.59999999999999998
string concat left and tree agree: true

Integer addition and string concatenation give the same result under either bracketing. Floating-point addition is commutative but not associative, because each operation rounds^[7], so a parallel sum of floats can differ in its last digits from a sequential one. Here the tree fold is the more accurate: it adds numbers of similar magnitude, and the left fold adds each small term to an ever larger total.

Incremental computation

Associativity also allows results to be cached and reused. If a sequence is stored in a balanced tree whose nodes hold the combination of their subtrees, changing one element requires recomputing only the combinations on its path to the root, $O (lo g n)$ of them, and the combination of any range is available in $O (lo g n)$ . Hinze and Paterson's finger trees are parameterized by such a monoid of measures, and the choice of monoid gives sequences, priority queues or interval trees from one data structure^[4]. Yorgey surveys how far this goes, including monoids acting on other monoids^[3].

§ 04

Homomorphisms and free monoids

A monoid homomorphism $h : M \to N$ preserves the identity and the operation:

h (e_{M}) = e_{N} h (a ⋄_{M} b) = h (a) ⋄_{N} h (b)

The length of lists is a homomorphism from lists under concatenation to $(N, +, 0)$ , and the logarithm one from $(R_{> 0}, \times, 1)$ to $(R, +, 0)$ . A homomorphism can be applied to the parts of a split computation and the results combined, which is what makes the map step of MapReduce compatible with the reduce step.

The lists over a set $A$ , written $A^{*}$ , form the free monoid on $A$ : every function $f : A \to M$ into a monoid extends uniquely to a homomorphism $f^: A^{*} \to M$ , namely

f^[a_{1}, \dots, a_{n}] = f (a_{1}) ⋄ \dots ⋄ f (a_{n})

which is the function called foldMap in Haskell. It is "free" because $A^{*}$ satisfies the monoid laws and nothing more: two lists are equal only if they are equal as sequences.

length as a homomorphism, and fold_map into three different monoids.

(* A monoid homomorphism preserves the unit and the operation. length maps
   the monoid of lists under append to the monoid of integers under +. *)
let length_hom xs ys = List.length (xs @ ys) = List.length xs + List.length ys
 
(* Lists are the free monoid: any function from elements into a monoid
   extends uniquely to a homomorphism from lists, fold_map f. *)
let fold_map (empty, op) f xs = List.fold_right (fun x acc -> op (f x) acc) xs empty

Running it.

length (xs @ ys) = length xs + length ys on 1000 random pairs: true
fold_map into (+):       19
fold_map into (max):     6
fold_map into (^):       tfmoas

In formal language theory $Σ^{*}$ is the free monoid of words over an alphabet, a language is a subset of it, and a finite automaton defines a homomorphism from words into a finite monoid of state transformations. Schützenberger characterized the star-free languages as those whose syntactic monoid has only trivial subgroups^[9].

§ 05

In functional programming

A fold over a collection with a monoid needs no starting value or combining function beyond the monoid's own, which is why Foldable can define sums, counts, searches and conversions to lists from a single foldMap. The writer monad accumulates output in a monoid alongside a computation^[11], and the constant functor into a monoid is an applicative functor, which is how a traversal collects values. Monoids that are commutative and idempotent, such as set union and maximum, are the basis of replicated data types that converge regardless of the order in which updates arrive.

§ 06

Category theory

A monoid is a category with one object: the elements are the arrows, composition is the operation and the identity arrow is $e$ . More generally, a monoid object in a monoidal category $(C, \otimes, I)$ is an object $M$ with arrows $μ : M \otimes M \to M$ and $η : I \to M$ satisfying the associativity and unit laws as commuting diagrams^[2]. Ordinary monoids are monoid objects in sets with the cartesian product. A monad is a monoid object in the category of endofunctors, with composition of functors as the tensor, $μ$ as join and $η$ as return^[2].

§ 07

History

Semigroups and monoids were studied in algebra from the early twentieth century as generalizations of groups, and the name monoid was standard by the time Bourbaki used it in the 1970 edition of Algèbre^[10]. Free monoids became central to computer science through formal language theory and automata in the 1950s and 1960s^[9]. In functional programming, the Monoid class became part of Haskell's standard library, and Steele's 2009 talk made the connection between associativity and parallelism widely known^[8].