Monoid

Accumulation, reduce operations

Publish at:
monoid algebraic-structure identity-element associativity fold reduce functional-programming category-theory 
 __  __  ___  _   _  ___ ___ ____  ____
|  \/  |/ _ \| \ | |/ _ \_ _|  _ \/ ___|
| |\/| | | | |  \| | | | | || | | \___ \
| |  | | |_| | |\  | |_| | || |_| |___) |
|_|  |_|\___/|_| \_|\___/___|____/|____/

Introduction #

Having explored semigroups and their associative operations, we now encounter a natural extension that adds even more power to our algebraic toolkit: monoids[1]. If semigroups gave us the ability to combine elements associatively, monoids give us something extra - a neutral element that doesn't change anything when combined with other elements.

Think of monoids as semigroups with a "do nothing" operation. This seemingly simple addition unlocks additional power.

From Semigroups to Monoids #

A monoid is essentially a semigroup enhanced with an identity element (also called a neutral element or unit). This identity element acts like zero in addition or one in multiplication - it leaves other elements unchanged when combined with them.

While semigroups are most naturally used with non-empty collections, monoids can also handle empty collections gracefully thanks to their identity element. This makes them useful for operations like:

  • Folding over empty lists
  • Initializing accumulator values
  • Providing default values in computations

Formal Definition #

A monoid is an algebraic structure consisting of:

  1. A set M (the underlying set or carrier)
  2. A binary operation ∘ : M × M -> M (closed under the operation)
  3. Associativity law: For all a, b, c ∈ M: (a ∘ b) ∘ c = a ∘ (b ∘ c)
  4. Identity element e ∈ M such that for all a ∈ M: e ∘ a = a ∘ e = a

The first three properties make a monoid a semigroup, and the fourth property - the identity element - is what distinguishes monoids from semigroups.

The Identity #

The identity element might seem trivial, but it provides crucial benefits:

Empty Case Handling: When folding over an empty collection, the identity element provides a meaningful default result.

Initialization: The identity element serves as a perfect starting point for accumulator-style computations.

Simplification: Many algorithms become simpler when they can assume an identity element exists.

Composability: Functions that return monoids can be safely composed, even when some return "empty" results.

Monoids as Single-Object Categories #

The identity element is not the only hidden gem of monoids. In addition, they provide an associative binary operation. Sounds familiar?

A regular category also has objects, morphisms, an associative composition law, and identity morphisms. Can you see it? Monoids have all the tools to form a category. Hence, every monoid can be viewed as a category with exactly one object.

Take a category with one object, regardless of the nature of that object:

  • Objects: just one, call it •. The single object • is fixed
  • Morphisms: Hom(•, •) = M, where
    • M is original monoid set
    • Hom(•, •) is the hom-set of arrows from • to itself
  • Composition: define categorical composition by g ∘ f = g * f - monoid operation
  • Identity: id_• = e. The identity arrow is the monoid unit
   •  --f-->  •
   •  --g-->  •
   •  --h-->  •

   Composition: g ∘ f = h   (defined by *)
   Identity:    id_• = e


 Monoid (M, *, e)                 Category C with object A
 -------------------              -------------------------
 | Elements: M     |              | Morphisms: Hom(A,A)    |
 | Operation: *    |   <------>   | Operation: ∘           |
 | Identity: e     |              | Identity: id_A         |
 -------------------              -------------------------
        |                                 |
        v                                 v
 Category with one object (•)      End(A) forms a monoid

Monoid ≅ Single-Object Category

Monoidal category definition #

There is also an ordinary category of monoids, whose objects are monoids and whose morphisms are monoid homomorphisms.[2] That should not be confused with a monoidal category, which is a different notion.

A monoidal category[3] is a category C equipped with:

  1. A tensor product functor ⊗ : C × C -> C
  2. A unit object I in C.
  3. Natural isomorphisms ensuring:
    • Associativity: (A ⊗ B) ⊗ C ≅ A ⊗ (B ⊗ C).
    • Unit laws: I ⊗ A ≅ A ≅ A ⊗ I.
  4. Coherence conditions ensuring these isomorphisms fit together consistently.

A monoidal category is an entire category equipped with a monoid-like structure. Tensor product ⊗ plays the role of the binary operation. Unit object I plays the role of the identity. Associativity and unit laws hold up to natural isomorphism.

Monoidal category of endofunctors #

An important example of a monoidal category is the category of endofunctors.

Category of endofunctors #

Endofunctors form a category (denoted End(C)):

  • Objects: The objects of End(C) are all endofunctors F: C -> C

  • Morphisms: The morphisms are natural transformations between endofunctors. For endofunctors F, G: C -> C, a morphism α: F ⟹ G in End(C) is a natural transformation where:

    • For each object A in C, we have a morphism α_A: F(A) -> G(A) in C
    • Naturality condition: For any morphism f: A -> B in C, the following diagram commutes:
    F(A) ----α_A----> G(A)
 |                  |
 |F(f)              |G(f)
 ▼                  ▼
F(B) ----α_B----> G(B)

    This means G(f) ∘ α_A = α_B ∘ F(f) for all morphisms f in C.

  • Identity: The identity natural transformation id_F: F ⟹ F where (id_F)_A = id_{F(A)} for each object A

  • Composition: Natural transformations compose component-wise:

    • Given α: F ⟹ G and β: G ⟹ H, their composition is β ∘ α: F ⟹ H
    • (β ∘ α)_A = β_A ∘ α_A for each object A

The collection of all endofunctors on a category C forms its own category, denoted End(C) or [C, C].

Monoidal category #

And how is it a monoidal category? Because End(C) has additional structure beyond just being a category.

Monoidal Product: Functor composition ∘ serves as the monoidal product

  • For endofunctors F, G: C -> C, their composition F ∘ G is also an endofunctor
  • Object mapping: (F ∘ G)(A) = F(G(A))
  • Morphism mapping: (F ∘ G)(f) = F(G(f))

Monoidal Unit: The identity functor Id_C: C -> C where Id_C(A) = A and Id_C(f) = f

Associativity: Functor composition is associative: (F ∘ G) ∘ H = F ∘ (G ∘ H)

Unit Laws: F ∘ Id_C = F = Id_C ∘ F for any endofunctor F

(Endofunctors on C, ∘, Id_C) is a monoidal category

Horizontal Composition of Natural Transformations #

In End(C), natural transformations can be composed both vertically (as morphisms in the category) and horizontally (using the monoidal structure):

Vertical Composition: Standard composition of natural transformations

  • (β ∘ α)_A = β_A ∘ α_A

This is ordinary composition of morphisms in the underlying category. It is literally the same pattern as: given f:A -> B, g:B -> C, their composite is (g ∘ f):A -> C.

A -- f --> B -- g --> C

Horizontal Composition: For natural transformations α: F ⟹ G and β: H ⟹ K:

  • α * β: F ∘ H ⟹ G ∘ K
  • Its component at A is (α * β)_A = G(β_A) ∘ α_{H(A)}
  • By naturality of α, this is equivalently α_{K(A)} ∘ F(β_A)

In a general monoidal category, this is a composition "side by side" using the tensor product ⊗. In End(C), that tensor product is functor composition. For ordinary morphisms f:A -> B and g:C -> D, the analogous tensor is f ⊗ g: A ⊗ C -> B ⊗ D.

A ----f----> B
              ⊗
C ----g----> D

Result:  (A ⊗ C) ----f ⊗ g----> (B ⊗ D)

This is "parallel composition": apply f and g independently, then combine the results with the tensor.

When we combine both horizontal and vertical composition, it is helpful to picture a two-dimensional grid like this:

   A --f--> B --f'--> C
   |        |        |
   g        g'       g''
   |        |        |
   D ------> E ------> F
  • Row-wise composition corresponds to ordinary composition inside each row.
  • The second direction represents composition across the other axis of the grid.
  • In End(C), these two directions correspond to vertical composition of natural transformations and horizontal composition induced by functor composition.

The Interchange Law #

When we have both kinds of composition (horizontal and vertical), they must cooperate. This is captured by the interchange law.

In a monoidal category, for morphisms:

  • f:A -> B, f':B -> C
  • g:D -> E, g':E -> F

the following equation holds:

(f′ ∘ f) ⊗ (g′ ∘ g) = (f′ ⊗ g′) ∘ (f ⊗ g)

   A⊗D -- f⊗g --> B⊗E -- f'⊗g' --> C⊗F

  = same as
           (f' ∘ f) ⊗ (g' ∘ g)
   A⊗D ----------------------------> C⊗F

So whether you compose first and then tensor, or tensor first and then compose, you get the same result.

Vertical then horizontal = horizontal then vertical

Take for example:

  • Set with Cartesian product

    • Vertical = usual composition of functions.
    • Horizontal = product of functions.

  • Endofunctors with composition:

    • Vertical = natural transformation composition.
    • Horizontal = horizontal composition of natural transformations induced by functor composition.

Examples #

Let's look at some common monoids that build upon the semigroups we've already explored:

Numbers Under Addition #

  • Set: All integers
  • Operation: Addition (+)
  • Identity: 0 (because 0 + x = x + 0 = x)
  • Associativity: (a + b) + c = a + (b + c)

Numbers Under Multiplication #

  • Set: All integers
  • Operation: Multiplication (*)
  • Identity: 1 (because 1 * x = x * 1 = x)
  • Associativity: (a * b) * c = a * (b * c)

Strings Under Concatenation #

  • Set: All strings
  • Operation: Concatenation (++)
  • Identity: Empty string "" (because "" ++ s = s ++ "" = s)
  • Associativity: (s1 ++ s2) ++ s3 = s1 ++ (s2 ++ s3)

Lists Under Concatenation #

  • Set: All lists of type [a]
  • Operation: List concatenation (++)
  • Identity: Empty list [] (because [] ++ xs = xs ++ [] = xs)
  • Associativity: (xs ++ ys) ++ zs = xs ++ (ys ++ zs)

Notice how each of these semigroups gains an identity element to become a monoid, making them easier to work with in practical applications.

Example usage #

Haskell has built-in support for monoids through the Monoid type class, which builds upon the Semigroup type class:

import Data.Monoid

-- Using Sum monoid for addition
example1 :: Int
example1 = getSum $ mconcat [Sum 1, Sum 2, Sum 3, Sum 4]
-- Result: 10

-- Using Product monoid for multiplication
example2 :: Int
example2 = getProduct $ mconcat [Product 2, Product 3, Product 4]
-- Result: 24

-- Working with strings (concatenation)
example3 :: String
example3 = mconcat ["Hello", " ", "World", "!"]
-- Result: "Hello World!"

-- Folding with empty case handling
safeSum :: [Int] -> Int
safeSum xs = getSum $ foldMap Sum xs
-- safeSum [] = 0 (identity element)
-- safeSum [1,2,3] = 6

-- Custom monoid for tracking statistics
data Stats = Stats { count :: Int, total :: Int } deriving (Show)

instance Semigroup Stats where
  Stats c1 t1 <> Stats c2 t2 = Stats (c1 + c2) (t1 + t2)

instance Monoid Stats where
  mempty = Stats 0 0

-- Usage: combining statistics from multiple sources
combineStats :: [Int] -> Stats
combineStats = foldMap (\x -> Stats 1 x)
-- combineStats [10, 20, 30] = Stats {count = 3, total = 60}
-- combineStats [] = Stats {count = 0, total = 0}

main :: IO ()
main = do
  print example1
  print example2
  print example3

  print $ safeSum [1,2,3]
  print $ safeSum []

  print $ combineStats [1, 2, 3]

// Monoid interface
interface Monoid<T> {
  empty: T;
  combine: (a: T, b: T) => T;
}

// String concatenation monoid
const StringMonoid: Monoid<string> = {
  empty: "",
  combine: (a, b) => a + b
};

// Number addition monoid
const NumberAddMonoid: Monoid<number> = {
  empty: 0,
  combine: (a, b) => a + b
};

// Array concatenation monoid
const ArrayMonoid = <T>(): Monoid<T[]> => ({
  empty: [],
  combine: (a, b) => [...a, ...b]
});

// Generic fold function that works with any monoid
function fold<T>(monoid: Monoid<T>, values: T[]): T {
  return values.reduce(monoid.combine, monoid.empty);
}

// Usage examples
const result1 = fold(StringMonoid, ["Hello", " ", "World"]);
// Result: "Hello World"

const result2 = fold(NumberAddMonoid, [1, 2, 3, 4, 5]);
// Result: 15

const result3 = fold(ArrayMonoid<number>(), [[1, 2], [3, 4], [5]]);
// Result: [1, 2, 3, 4, 5]

// Safe operations with empty collections
const emptySum = fold(NumberAddMonoid, []);
// Result: 0 (identity element)

// Custom monoid for shopping cart
interface CartItem {
  quantity: number;
  price: number;
}

const CartMonoid: Monoid<CartItem> = {
  empty: { quantity: 0, price: 0 },
  combine: (a, b) => ({
    quantity: a.quantity + b.quantity,
    price: a.price + b.price
  })
};

const cart = fold(CartMonoid, [
  { quantity: 2, price: 10.50 },
  { quantity: 1, price: 25.00 },
  { quantity: 3, price: 7.25 }
]);
// Result: { quantity: 6, price: 42.75 }

console.log(result1, result2, result3, emptySum, cart);

using System;
using System.Collections.Generic;
using System.Linq;

// Monoid interface
public interface IMonoid<T>
{
    T Identity { get; }
    T Combine(T a, T b);
}

// String concatenation monoid
public class StringConcatMonoid : IMonoid<string>
{
    public string Identity => string.Empty;

    public string Combine(string a, string b) => a + b;
}

// Integer addition monoid
public class IntAddMonoid : IMonoid<int>
{
    public int Identity => 0;

    public int Combine(int a, int b) => a + b;
}

// List concatenation monoid
public class ListConcatMonoid<T> : IMonoid<List<T>>
{
    public List<T> Identity => new List<T>();

    public List<T> Combine(List<T> a, List<T> b)
    {
        var result = new List<T>(a);
        result.AddRange(b);
        return result;
    }
}

// Extension methods for monoid operations
public static class MonoidExtensions
{
    public static T Fold<T>(this IEnumerable<T> source, IMonoid<T> monoid)
    {
        return source.Aggregate(monoid.Identity, monoid.Combine);
    }

    public static T FoldMap<TSource, T>(
        this IEnumerable<TSource> source,
        Func<TSource, T> selector,
        IMonoid<T> monoid)
    {
        return source.Select(selector).Fold(monoid);
    }
}

// Usage examples
class Program
{
    static void Main()
    {
        var stringMonoid = new StringConcatMonoid();
        var intMonoid = new IntAddMonoid();
        var listMonoid = new ListConcatMonoid<int>();

        // String concatenation
        var words = new[] { "Hello", " ", "World", "!" };
        var sentence = words.Fold(stringMonoid);
        Console.WriteLine(sentence); // "Hello World!"

        // Number addition
        var numbers = new[] { 1, 2, 3, 4, 5 };
        var sum = numbers.Fold(intMonoid);
        Console.WriteLine(sum); // 15

        // List concatenation
        var lists = new[]
        {
            new List<int> { 1, 2 },
            new List<int> { 3, 4 },
            new List<int> { 5 }
        };
        var combined = lists.Fold(listMonoid);
        Console.WriteLine(string.Join(", ", combined)); // "1, 2, 3, 4, 5"

        // Safe empty collection handling
        var emptySum = new int[0].Fold(intMonoid);
        Console.WriteLine(emptySum); // 0 (identity element)

        // Custom monoid for order totals
        var orders = new[] { 10.50m, 25.00m, 7.25m, 15.75m };
        var total = orders.FoldMap(x => x, new DecimalAddMonoid());
        Console.WriteLine($"Total: ${total}"); // "Total: $58.50"
    }
}

// Custom decimal addition monoid
public class DecimalAddMonoid : IMonoid<decimal>
{
    public decimal Identity => 0m;

    public decimal Combine(decimal a, decimal b) => a + b;
}

Triangle Monoid Example #

Building upon the triangle semigroup from our previous chapter, we have to be a bit more careful. The centroid-based triangle operation does not come with an obvious geometric identity triangle.

The Set and Operation #

To obtain a monoid from that semigroup, we adjoin a new formal identity element e:

  • Set: All triangles in 2D space, together with a new symbol e
  • Operation: The same triangle combination operation from the semigroup, extended by the rules e ∘ T = T and T ∘ e = T
  • Identity: e

This e is an extra element added so the operation has a true identity. That construction is standard: any semigroup can be turned into a monoid by adjoining an identity element.

Visual Representation #

Adjoined identity:
    e

Combining with identity:
    e ∘ △ = △
    △ ∘ e = △

Regular triangle combination:
    △₁ ∘ △₂ = △₃

    Where △₃ is formed by:
    - Centroid of △₁ as first vertex
    - Centroid of △₂ as second vertex
    - Midpoint between centroids as third vertex

Let's see how triangle combination works step by step:

Step 1: Original Triangles

Triangle A:           Triangle B:
    A                     D
   /|\                   /|\
  / | \                 / | \
 /  |  \               /  |  \
B---+---C             E---+---F
    ↑                     ↑
  A_centroid            B_centroid

Step 2: Extract Centroids

Centroid A: ● (x₁,y₁)
Centroid B: ● (x₂,y₂)

Step 3: Calculate Midpoint

Midpoint M: ● ((x₁+x₂)/2, (y₁+y₂)/2)

Step 4: Form New Triangle

Result Triangle (A ∘ B):

    Centroid_A ●
              /|\
             / | \
            /  |  \
Centroid_B ●---+---● Midpoint_M

With Coordinates:

Triangle A: (0,3), (0,0), (3,0)    Triangle B: (5,2), (4,0), (6,0)

     A(0,3)                           D(5,2)
     /|\                             /|\
    / | \                           / | \
   /  |  \                         /  |  \
B(0,0)-+-C(3,0)                 E(4,0)-+-F(6,0)
      ↑                               ↑
   Centroid A                     Centroid B
   (1, 1)                         (5, 0.67)

Combination Process:
1. A_centroid = (1, 1)
2. B_centroid = (5, 0.67)
3. Midpoint = (3, 0.835)

Result Triangle:

         A_centroid(1,1)  ●
                         /|\
                        / | \
                       /  |  \
   B_centroid(5,0.67) ●---+---● Midpoint(3,0.835)

Identity Element Behavior:

Formal Identity + Any Triangle = That Triangle

e ∘ Triangle A:
                  A             A
    e            /|\     =     /|\
 (formal unit)  / | \         / | \
               /  |  \       /  |  \
              B---+---C     B---+---C

Triangle A ∘ e:
    A                          A
   /|\           e      =     /|\
  / | \    (formal unit)     / | \
 /  |  \                    /  |  \
B---+---C                  B---+---C

CSV Transform example #

Continuing semigroup CSV Transform example, let's see how monoids enhance data processing by providing safe empty case handling and initialization.

With monoids we gain additional benefits:

  • 🔧 Safe Empty Datasets: No errors when processing empty CSV files
  • 🚀 Default Initialization: Perfect starting values for accumulator operations
  • 🎯 Simplified Processing: No need for special empty case handling
  • ⚡ Parallel-Ready: Safe chunking and load balancing without edge cases
  • 📊 Robust Statistics: Always valid results even with missing data
  • 👥 Person Combination: Enhanced merging with identity element safety
  • ➕ Age Summation: Zero-safe addition that works with empty collections
  • 📋 Name Collection: Safe concatenation that handles empty lists gracefully
  • 🗂️ Dataset Merging: Combines multiple CSV datasets including empty ones
  • 🛡️ Error Recovery: Failed operations contribute identity elements safely

Visualizing monoids #

Monoid = Set + Operation + Laws

     SET: {a, b, c, d, e, ...}
      │
      ├─ OPERATION: ∘ (binary, closed, associative)
      │
      └─ IDENTITY: e (neutral element)

Laws:
1. Closure:      a ∘ b ∈ Set
2. Associativity: (a ∘ b) ∘ c = a ∘ (b ∘ c)
3. Identity:     e ∘ a = a ∘ e = a

-------------------------------------------------------

Identity Element (e) acts as "do nothing":

    a ∘ e = a        e ∘ a = a
    │   │   │        │   │   │
    │   │   └────────┘   │   │
    │   └──────────────────  │
    └────────────────────────┘
         Same element 'a'

Left-associative:  ((a ∘ b) ∘ c) ∘ d
                    │─────│
                    │  r₁ │
                    │─────────│
                    │   r₂    │
                    │─────────────│
                    │    r₃       │

Right-associative: a ∘ (b ∘ (c ∘ d))
                           │─────│
                           │  r₁ │
                       │─────────│
                       │   r₂    │
                   │─────────────│
                   │    r₃       │

Both produce the same result: r₃

-------------------------------------------------------

Decomposition:

Original data: [a, b, c, d, e, f, g, h]

Split into chunks:
┌─────────┬─────────┬─────────┬─────────┐
│ [a, b]  │ [c, d]  │ [e, f]  │ [g, h]  │
└─────────┴─────────┴─────────┴─────────┘
     │         │         │         │
   Worker 1  Worker 2  Worker 3  Worker 4
     │         │         │         │
   a ∘ b     c ∘ d     e ∘ f     g ∘ h
     │         │         │         │
    r₁        r₂        r₃        r₄

Combine results:
(r₁ ∘ r₂) ∘ (r₃ ∘ r₄) = final result

Empty chunks are safe:
┌─────────┬─────────┬─────────┬─────────┐
│ [a, b]  │   []    │ [e, f]  │ [g, h]  │
└─────────┴─────────┴─────────┴─────────┘
     │         │         │         │
   a ∘ b       e       e ∘ f     g ∘ h
     │         │         │         │
    r₁        r₂        r₃        r₄

Still works: (r₁ ∘ e) ∘ (r₃ ∘ r₄) = r₁ ∘ (r₃ ∘ r₄)

Semigroup vs Monoid Comparison #

Semigroup (no identity):
  ┌─────────────────────────────────┐
  │  SET + ASSOCIATIVE OPERATION    │
  │                                 │
  │  ⚠️  fold([]) = ERROR           │
  │  ✅  fold([a]) = a              │
  │  ✅  fold([a,b,c]) = (a∘b)∘c    │
  └─────────────────────────────────┘

Monoid (with identity):
  ┌─────────────────────────────────┐
  │  SET + ASSOCIATIVE OPERATION    │
  │         + IDENTITY ELEMENT      │
  │                                 │
  │  ✅  fold([]) = e               │
  │  ✅  fold([a]) = a              │
  │  ✅  fold([a,b,c]) = (a∘b)∘c    │
  └─────────────────────────────────┘

The identity element makes monoids much safer!

Parallel processing #

Building upon the parallel processing patterns from semigroups, monoids provide even greater advantages for parallel computation. The identity element eliminates the need for special handling of empty collections and provides guaranteed safe initialization values. Let's explore how monoids excel in parallel scenarios:

Key Advantages of Monoids in Parallel Processing #

  1. Empty Collection Safety: No need for Maybe/Optional types - empty collections fold to the identity element
  2. Guaranteed Initialization: Every parallel worker can start with the identity element
  3. Simplified Load Balancing: Uneven chunk distribution doesn't require special handling
  4. Robust Error Recovery: Failed workers can be replaced with identity elements

Conclusion #

Monoids provide a perfect foundation for many common programming patterns:

  • Reduce operations: When you need to combine all elements in a collection
  • Default values: The identity element provides a sensible default for empty cases
  • Incremental computation: Building up results step by step with guaranteed correctness
  • Parallel processing: The associativity and identity properties enable safe parallelization
  • Compositional design: Monoids compose naturally, making complex systems easier to reason about

Source code #

Reference implementation

References

  1. Monoid ·
  2. Category of monoids ·
  3. Monoidal category ·

Continue exploring