Monoids and fold: combine many into one

Lesson 08 gave us the functor: a way to transform each value inside a context with map, without disturbing the context. But mapping never reduces — a list of a thousand numbers stays a thousand numbers. The complementary move is to combine them all into a single summary: a sum, a concatenation, a maximum, a merged config. This lesson names the precise algebraic pattern that makes "combine a bunch of things" safe and reorderable — the monoid — and the operation that drives it through a whole collection — fold. The single new idea: an associative binary operation with an identity element lets you collapse many values into one in any grouping, which is exactly what makes the collapse parallelizable.

Book source

Maps to Widman's treatment of monoids as the first concrete algebraic structure — a set with a well-behaved combining operation — and to fold/reduce as the canonical way to consume an immutable collection. We reuse the laws vocabulary from Lesson 07 (associativity and identity were already the axioms of a category) and the reduce-as-a-HOF idea from Lesson 05. Prose and examples are original.

Linear position

Prerequisite: Lesson 07 (laws — associativity and identity as the things that make composition predictable) and Lesson 05 (reduce as a higher-order function that walks a collection combining elements pairwise).
New capability: recognize a monoid in the wild — a type with an associative combine and an empty identity — and use foldLeft/foldRight to collapse any collection into one value, knowing precisely when the collapse is safe, reorderable, and parallelizable.

The plan

Five moves. (1) Motivate: "summarize a collection" is everywhere, and a monoid is the exact pattern that makes it safe. (2) Define the monoid — a type, an associative combine, an identity empty — and write the Scala trait. (3) Tour a gallery of instances, checking each against the two laws, plus two non-examples so the laws bite. (4) Show why associativity is the whole payoff: grouping stops mattering, so the fold splits across chunks — this is MapReduce. (5) Meet foldLeft/foldRight, fold a list with a monoid, and see that reduce is fold minus the identity (and thus unsafe on empty input).

1 · The recurring shape: collapse a collection to a summary

Look at how often a program takes a pile of values and produces one: total a list of prices; concatenate log lines into a report; find the largest response time; flatten a list of lists; AND together a list of permission checks; merge a sequence of config overrides into one effective config. These feel like different tasks, but they share a skeleton. In each, you have a type of thing, a way to combine two of them into one of the same type, and a sensible starting value for "nothing yet." That shared skeleton has a name, and pinning it down tells you exactly when the combine is trustworthy — when you can reorder it, chunk it, or run it empty without surprises.

2 · The monoid: a type, an associative combine, an identity

A monoid is three things bundled together: a type A; a binary operation combine(x: A, y: A): A (often written a ⊕ b) that takes two values of A and returns an A; and a distinguished value empty: A. They must obey exactly two laws.

associativity: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) identity: empty ⊕ a = a ⊕ empty = a

Associativity says the way you parenthesize a chain of combines does not change the result — only the left-to-right order of the elements matters, not how you group them. Identity says empty is a neutral element: combining anything with empty gives that thing back unchanged. Note what is not required: commutativity (a ⊕ b = b ⊕ a) is not part of the definition. String concatenation is a monoid but is not commutative, so the element order still matters — only the grouping is free.

In Scala the bundle is naturally a trait parameterized by the type. This is the type-class shape — an interface describing a capability of a type, supplied separately from the type itself — which Lesson 14 develops fully with given/implicit; here we just pass instances by hand.

trait Monoid[A] {
  def empty: A                    // the identity element
  def combine(x: A, y: A): A      // the associative binary op  (a ⊕ b)
}

3 · A gallery of instances — and two non-examples

Every monoid below is just a value of Monoid[A] for some A. After each, mentally check the two laws — that habit is the whole skill.

val intAdd  = new Monoid[Int]    { def empty = 0;            def combine(x: Int, y: Int)   = x + y }
val intMul  = new Monoid[Int]    { def empty = 1;            def combine(x: Int, y: Int)   = x * y }
val strCat  = new Monoid[String] { def empty = "";           def combine(x: String, y: String) = x + y }
val boolAnd = new Monoid[Boolean]{ def empty = true;         def combine(x: Boolean, y: Boolean) = x && y }
val intMax  = new Monoid[Int]    { def empty = Int.MinValue; def combine(x: Int, y: Int)   = x max y }
def listCat[A] = new Monoid[List[A]] { def empty = Nil;      def combine(x: List[A], y: List[A]) = x ++ y }

(Int, +, 0)

(a+b)+c = a+(b+c) ✓; 0+a = a+0 = a ✓. The canonical monoid: summation.

(Int, ×, 1)

Multiplication is associative; 1×a = a. Identity is 1, not 0 — picking 0 would annihilate every product.

(String, ++, "")

Concatenation is associative; the empty string is neutral. Associative but not commutative — "ab" ≠ "ba" — and that is allowed.

(List, ++, Nil)

List concatenation associates; Nil ++ xs = xs. The same shape as String, which is no accident — both are free monoids.

(Boolean, &&, true)

&& associates; true && b = b. (|| with identity false is another.) Folds a list of checks into one verdict.

(Int, max, Int.MinValue)

max associates; Int.MinValue max a = a since nothing is smaller. The "no data yet" maximum must be the smallest possible value.

Two non-examples — where the laws bite

Subtraction (a − b) is not associative: (5 − 3) − 2 = 0 but 5 − (3 − 2) = 4. Grouping changes the answer, so subtraction is not a monoid — you cannot safely chunk a "fold by subtraction." Averaging has no identity: there is no number e such that avg(e, a) = a for all a, and averaging is not associative either (avg(avg(1,2),3) ≠ avg(1,avg(2,3))). The fix is to fold the monoid (sum, count) pairwise and divide once at the end — average is a function of a monoid, not a monoid.

4 · Why associativity is the entire payoff

Here is the cash value of the associativity law. Because grouping does not matter, a long chain a₁ ⊕ a₂ ⊕ … ⊕ aₙ can be parenthesized however you like and still give the same result. So split the collection into chunks, combine each chunk independently — on different cores, different machines — then combine the chunk-results. The empty element gives every chunk (even an empty one) a safe starting value. That is precisely the algebra behind MapReduce: map turns each record into a monoid value, and reduce combines them associatively, in any order the cluster finds convenient. Without associativity the reducer's grouping would change the answer and parallelism would be unsound. A monoid is the contract that licenses the split.

5 · Fold: driving the monoid through a collection

To actually consume a list, Scala gives you foldLeft and foldRight. Each takes a seed z and a binary op, then walks the list applying op between the accumulator and each element. Folding with a monoid means: seed with empty, combine with combine.

def combineAll[A](xs: List[A])(m: Monoid[A]): A =
  xs.foldLeft(m.empty)(m.combine)        // empty ⊕ x1 ⊕ x2 ⊕ … ⊕ xn

combineAll(List(1, 2, 3, 4))(intAdd)     // 10
combineAll(List("a","b","c"))(strCat)    // "abc"
combineAll(List.empty[Int])(intAdd)      // 0  — empty input gives the identity, no crash

The two folds differ in association direction. foldLeft(z)(op) nests to the left, ((z⊕a)⊕b)⊕c, walking front-to-back with an accumulator — a loop, stack-safe for any length. foldRight(z)(op) nests to the right, a⊕(b⊕(c⊕z)), which on a plain List must hold every element "open" until the innermost combine returns — a hazard on long inputs that Lesson 12 makes precise (it is the difference between a recursion that loops and one that piles up, and the fix is tail recursion). For a monoid, associativity guarantees both directions give the same value — so until Lesson 12 explains the mechanism, just prefer foldLeft. reduce (from Lesson 05) is fold without the identity: it uses the first element as the seed, so on an empty collection there is nothing to start from and it throws — a partial function in the sense of Lesson 06. The identity is exactly what upgrades the unsafe reduce into a total fold.

Worked example — grouping is free, so chunks parallelize

Fold List(1, 2, 3, 4) under (+, 0).
Left grouping (foldLeft): (((0 + 1) + 2) + 3) + 4 = ((1 + 2) + 3) + 4 = (3 + 3) + 4 = 6 + 4 = 10.
Right grouping (foldRight): 1 + (2 + (3 + (4 + 0))) = 1 + (2 + (3 + 4)) = 1 + (2 + 7) = 1 + 9 = 10.
Same answer — because + is associative; for subtraction these two would disagree. Now split into halves and combine in parallel: chunk A = 1 + 2 = 3, chunk B = 3 + 4 = 7 (computed on separate cores), then 3 + 7 = 10. The same total falls out no matter how we carve the list — which is the whole license to parallelize.

Common mistakes / failure modes

Assuming any binary op associates

Subtraction, division, and averaging are not associative, so folding with them gives grouping-dependent answers and cannot be chunked. Always check (a⊕b)⊕c = a⊕(b⊕c) before treating an op as a monoid.

Wrong / missing identity

Using 0 for multiplication (annihilates everything), 0 for max (wrong on all-negative inputs), or ""-like guesses for a type with no neutral value. The identity must satisfy empty ⊕ a = a for every a.

Reaching for reduce on maybe-empty input

reduce has no seed, so it throws on an empty collection — a partiality bug (Lesson 06). When the input might be empty, use foldLeft(empty)(combine); the identity supplies the answer for "nothing."

Confusing associativity with commutativity

A monoid needs only associativity. String/List concatenation reorder the elements at your peril, but grouping is still free. Don't assume a⊕b = b⊕a unless you've checked it.

Checkpoint exercise

Try it

(a) Does (Int, min) form a monoid? It needs an identity e with min(e, a) = a for every Int. Name that e and confirm min is associative. (Hint: mirror the max instance — what is the largest possible Int?) (b) Write the generic collapser def combineAll[A](xs: List[A])(m: Monoid[A]): A using a fold, then call it with your min monoid on List(7, 2, 9, 2) and on List.empty[Int] — predict both results before running. What does the empty case return, and why is that the correct "minimum of nothing"?

Where this points next

We now hold two of the three escalating powers from the spine: Lesson 08 let us map a function over the values inside a context (transform without leaving the box), and this lesson let us combine many values into one whenever they form a monoid. Lesson 10 adds the third and the capstone: the monad. Mapping cannot sequence dependent steps — when each step itself returns a context (an Option, a List, a Future), map leaves you with a nested F[F[A]] that combining alone won't flatten. The monad's flatMap threads context-carrying steps in order, and Scala's for-comprehension makes that sequencing read like ordinary code.

Takeaway

A monoid is a type A with an associative combine ((a⊕b)⊕c = a⊕(b⊕c)) and an identity empty (empty⊕a = a⊕empty = a) — the precise pattern behind summing, concatenating, max, AND-ing, and merging. Associativity is the payoff: because grouping does not matter, a fold can split a collection into chunks, combine them independently, and recombine in any order — the algebra under MapReduce — while empty supplies the safe "nothing yet" value. Drive it through a collection with xs.foldLeft(empty)(combine); reduce is the same minus the identity and therefore throws on empty input. Check the two laws on every candidate (subtraction, division, and averaging fail), and you'll always know when "combine a bunch of things" is safe and reorderable.

Interview prompts

Define a monoid precisely and state its two laws. (§2 — a type A, an associative binary combine, and an identity empty; laws are (a⊕b)⊕c = a⊕(b⊕c) and empty⊕a = a⊕empty = a. Commutativity is not required.)
Give three monoids over different types and their identities. (§3 — (Int,+,0), (Int,×,1), (String,++,""), (List,++,Nil), (Boolean,&&,true), (Int,max,Int.MinValue) — note ×'s identity is 1, max's is the smallest value.)
Why is associativity, not commutativity, the property that enables parallelism? (§4 — associativity means grouping is free, so the collection can be chunked, each chunk combined independently, and the results recombined in any grouping — MapReduce. Order of elements can still matter.)
Show that subtraction is not a monoid. (§3 — not associative: (5−3)−2 = 0 but 5−(3−2) = 4; grouping changes the result, so a fold by subtraction is grouping-dependent and not chunkable.)
What is the difference between fold and reduce, and when does it matter? (§5 — fold takes an identity seed and is total; reduce uses the first element and throws on empty input. With possibly-empty data, prefer foldLeft(empty)(combine).)
How do foldLeft and foldRight differ, and why does it not change a monoid's result? (§5 — they associate left vs right and differ in stack behavior on List; associativity guarantees the same value, so prefer the stack-safe foldLeft. Lesson 12 covers the stack story.)
How would you compute an average over a stream functionally? (§3 non-example — averaging is neither associative nor has an identity, so fold the monoid (sum, count) pairwise and divide once at the end; average is a function of a monoid, not a monoid.)