Free Monoids

Bartosz Milewski · 2015 · Category Theory for Programmers, Ch. 12

Prereqs: 🍞 Ch3 (Categories Great and Small — monoids). 7 min.

The free monoid on a set of generators is the list type. Lists are the cheapest way to make concatenation associative with an identity element (the empty list). Any function from generators into a monoid extends uniquely to a monoid homomorphism from the free monoid: that extension is fold.

Monoids: a set with a binary operation

A monoid is a set with an associative binary operation and an identity element. Strings under concatenation, numbers under addition, lists under append. The question this chapter answers: given a raw set of generators, what is the most general monoid you can build from them?

Scheme

; A monoid needs: a set, a binary op, and an identity.
; (m, mappend, mempty) such that:
;   mappend(mappend(a, b), c) = mappend(a, mappend(b, c))
;   mappend(mempty, a) = a
;   mappend(a, mempty) = a

; Numbers under addition
(define (add-mappend a b) (+ a b))
(define add-mempty 0)

; Strings under concatenation
(define (str-mappend a b) (string-append a b))
(define str-mempty "")

(display "3 + 4 = ") (display (add-mappend 3 4)) (newline)
(display "0 + 5 = ") (display (add-mappend add-mempty 5)) (newline)
(display "\"hello\" ++ \" world\" = ")
(display (str-mappend "hello" " world")) (newline)
(display "\"\" ++ \"abc\" = ")
(display (str-mappend str-mempty "abc"))

Free construction: add structure, nothing extra

A free construction takes a plain set and builds the most general algebraic structure from it. "Most general" means: impose only the laws the structure requires (associativity, identity), and no additional equations. Starting from generators {a, b}, the free monoid contains e, a, b, aa, ab, ba, bb, aab, ...: all finite sequences, with concatenation as the operation. No element equals any other unless the monoid laws force it.

Scheme

; Free monoid on generators {a, b}:
; All finite sequences of a's and b's.
; Concatenation is the operation. Empty list is the identity.

(define generators '(a b))

; The free monoid elements are lists of generators
(define e '())          ; identity
(define just-a '(a))
(define just-b '(b))
(define ab '(a b))
(define ba '(b a))
(define aab '(a a b))

; The monoid operation is append
(define (free-mappend xs ys) (append xs ys))
(define free-mempty '())

; Associativity: (ab)(ba) = a(bb)a? No — they're different lists.
; The free monoid makes NO extra identifications.
(display "ab * ba = ") (display (free-mappend ab ba)) (newline)
(display "a * ab  = ") (display (free-mappend just-a ab)) (newline)
(display "e * aab = ") (display (free-mappend free-mempty aab)) (newline)
(display "aab * e = ") (display (free-mappend aab free-mempty))
; Lists are the free monoid.

The universal property

The free monoid on a set x is defined by a universal property. Given any function q : x -> U(n) from the generators into the underlying set of some monoid n, there exists a unique monoid homomorphism h : free(x) -> n that extends q. The forgetful functor U strips a monoid down to its underlying set. The free construction is its left adjoint: the cheapest way to promote a set to a monoid.

Scheme

; Universal property of free monoids:
;
; Given: generators x, a monoid n, a function q : x -> U(n)
; There exists a UNIQUE homomorphism h : free(x) -> n
; such that h(embed(g)) = q(g) for each generator g.
;
; In code: h = fold guided by q.

; Generators: {a, b}
; Target monoid: (integers, *, 1)
; q maps: a -> 2, b -> 3

(define (q gen)
  (cond ((eq? gen 'a) 2)
        ((eq? gen 'b) 3)))

; The unique homomorphism is fold:
; h([]) = 1 (identity of target)
; h([g1, g2, ...]) = q(g1) * q(g2) * ...

(define (h xs)
  (fold-right * 1 (map q xs)))

; Check it's a homomorphism: h(xs ++ ys) = h(xs) * h(ys)
(define xs '(a b))    ; h = 2*3 = 6
(define ys '(b a a))  ; h = 3*2*2 = 12

(display "h(ab)  = ") (display (h xs)) (newline)
(display "h(baa) = ") (display (h ys)) (newline)
(display "h(ab ++ baa) = ") (display (h (append xs ys))) (newline)
(display "h(ab) * h(baa) = ") (display (* (h xs) (h ys))) (newline)
; 72 = 72. The homomorphism property holds.

Monoid homomorphisms: structure-preserving maps

A monoid homomorphism is a function between monoids that preserves the operation and the identity. If h(a * b) = h(a) * h(b) and h(e) = e', then h is a homomorphism. The universal property says the homomorphism from a free monoid is determined entirely by where the generators go. No choice remains.

Scheme

; Monoid homomorphism: preserves operation and identity.
; h(a * b) = h(a) * h(b)
; h(e) = e'

; Example: length is a homomorphism from (lists, append, [])
; to (integers, +, 0)

(define (h-length xs) (length xs))

(define xs '(a b c))
(define ys '(d e))

(display "h([a,b,c]) = ") (display (h-length xs)) (newline)
(display "h([d,e])   = ") (display (h-length ys)) (newline)
(display "h([a,b,c] ++ [d,e]) = ")
(display (h-length (append xs ys))) (newline)
(display "h([a,b,c]) + h([d,e]) = ")
(display (+ (h-length xs) (h-length ys))) (newline)
; 5 = 5. Length preserves the structure.

(display "h([]) = ") (display (h-length '()))
; 0 — identity maps to identity.

Fold: the universal homomorphism

Here is the punchline in code. fold (or reduce) is the unique homomorphism guaranteed by the universal property. You give it a function from generators to a target monoid and the target's identity. It does the only thing it can: apply the function to each generator and combine the results with the target's operation. There is no other homomorphism that agrees on the generators.

Scheme

; fold IS the universal homomorphism.
; Given q : generators -> monoid, fold extends q to lists -> monoid.

; Target 1: (string, ++, "")
; q maps each symbol to its string name
(define (q1 gen) (symbol->string gen))

(define (h1 xs)
  (fold-right string-append "" (map q1 xs)))

(display "h1([hello world]) = ")
(display (h1 '(hello world))) (newline)

; Target 2: (bool, and, #t)
; q maps: 'yes -> #t, 'no -> #f
(define (q2 gen)
  (eq? gen 'yes))

(define (h2 xs)
  (fold-right (lambda (a b) (and a b)) #t (map q2 xs)))

(display "h2([yes yes]) = ") (display (h2 '(yes yes))) (newline)
(display "h2([yes no])  = ") (display (h2 '(yes no))) (newline)
(display "h2([])        = ") (display (h2 '())) (newline)
; Empty list maps to #t (identity of and-monoid).
; Each fold is uniquely determined by where the generators go.

Free means no extra equations

Any monoid with elements from a set of generators is a quotient of the free monoid: take the free monoid and identify some elements. The integers under addition are the free monoid on one generator (the natural numbers and their negatives, a.k.a. lists of +1 and -1). But the integers mod 3 are a quotient: 0 = 3 = 6 = .... The free monoid makes the fewest identifications possible. Every other monoid makes more.

Scheme

; Free monoid on one generator = natural numbers (under +)
; (lists of length n, append, []) ~ (n, +, 0)
;
; Quotient: integers mod 3
; The free monoid says (a a a) != ()
; The quotient says    (a a a) = ()

; Free: all distinct
(define (free-eq? xs ys) (equal? xs ys))

(display "free: (a a a) = ()? ")
(display (free-eq? '(a a a) '())) (newline)

; Quotient mod 3: identify by length mod 3
(define (mod3-eq? xs ys)
  (= (modulo (length xs) 3)
     (modulo (length ys) 3)))

(display "mod3: (a a a) = ()? ")
(display (mod3-eq? '(a a a) '())) (newline)
(display "mod3: (a) = (a a a a)? ")
(display (mod3-eq? '(a) '(a a a a))) (newline)
; The quotient adds equations. The free monoid has none.

Notation reference

Blog / Haskell	Scheme	Meaning
[a]	(list 'a 'b ...)	Free monoid (list of generators)
[] (mempty)	'()	Identity element (empty list)
++ (mappend)	(append xs ys)	Monoid operation (concatenation)
U : Mon -> Set	(forgetful functor)	Strips monoid structure, keeps the set
h : free(x) -> n	(fold-right op e (map q xs))	Unique homomorphism (fold)
foldMap f	(fold-right op e (map f xs))	Map generators then fold with target op

Neighbors

Milewski chapters

🍞 Chapter 3 — Categories Great and Small: where monoids are introduced
(next) Chapter 13 — Representable Functors

Foundations (Wikipedia)

Translation notes

The blog post defines free monoids via a universal construction in the category Mon of monoids, using the forgetful functor U : Mon -> Set and ranking candidates by the existence of unique homomorphisms. This page skips the categorical machinery and works directly with lists and fold. The key correspondence: Haskell's foldMap :: Monoid m => (a -> m) -> [a] -> m is the concrete implementation of the universal homomorphism. Give it a function from generators to any monoid, and it produces the unique structure-preserving map. The blog post also discusses how every monoid is a quotient of a free monoid. This page illustrates that with mod-3 arithmetic, but the full picture involves equivalence relations on the free monoid that are compatible with concatenation (i.e., congruences).

Ready for the real thing? Read the blog post. Start with the universal construction, then see how lists emerge as the answer.

← Limits and Colimits by june.kim Representable Functors →