229 Advanced

Monoid as a Category

Category Theory

Tutorial Video

Text description (accessibility)

This video demonstrates the "Monoid as a Category" functional Rust example. Difficulty level: Advanced. Key concepts covered: Category Theory. Model a monoid as a single-object category where morphisms are monoid elements and composition is the monoid's binary operation. Key difference from OCaml: 1. **Abstraction mechanism:** OCaml uses first

Tutorial

The Problem

Model a monoid as a single-object category where morphisms are monoid elements and composition is the monoid's binary operation. Verify the monoid laws (identity and associativity) and demonstrate folding morphisms as categorical composition.

🎯 Learning Outcomes

• How Rust traits encode algebraic structures like Monoid

• How generic functions enforce and verify algebraic laws at compile time

• The correspondence between fold and categorical composition of morphisms

• How newtypes (StringMonoid, SumMonoid, …) allow multiple monoid instances per underlying type

🦀 The Rust Way

Rust expresses the same ideas with a Monoid trait and generic functions bounded by Monoid + PartialEq + Clone. Newtypes wrap primitive types so multiple monoid instances can coexist without orphan-rule conflicts. Folding morphisms is Iterator::fold with M::empty() as the accumulator, exactly mirroring OCaml's fold_left.

Code Example

pub trait Monoid {
    fn empty() -> Self;
    fn append(self, other: Self) -> Self;
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct StringMonoid(pub String);

impl Monoid for StringMonoid {
    fn empty() -> Self { StringMonoid(String::new()) }
    fn append(self, other: Self) -> Self { StringMonoid(self.0 + &other.0) }
}

pub fn compose_morphisms<M: Monoid>(morphisms: impl IntoIterator<Item = M>) -> M {
    morphisms.into_iter().fold(M::empty(), |acc, m| acc.append(m))
}

module type MONOID = sig
  type t
  val empty  : t
  val append : t -> t -> t
end

module MonoidLaws (M : MONOID) = struct
  let check_identity x =
    M.append M.empty x = x &&
    M.append x M.empty = x

  let check_associativity x y z =
    M.append (M.append x y) z = M.append x (M.append y z)
end

module StringMonoid : MONOID with type t = string = struct
  type t = string
  let empty  = ""
  let append = ( ^ )
end

let compose_morphisms ms =
  List.fold_left StringMonoid.append StringMonoid.empty ms

Key Differences

Abstraction mechanism: OCaml uses first-class modules/functors; Rust uses traits and generics.

Multiple instances: OCaml defines separate named modules; Rust uses newtypes to give distinct impl Monoid blocks to the same base type.

Identity element: OCaml's val empty : t is a value; Rust's fn empty() -> Self is a static method (required because Rust has no top-level val).

Law checking: OCaml's MonoidLaws functor is instantiated per type; Rust's law functions are generic over M: Monoid + PartialEq + Clone, applied at call site.

OCaml Approach

OCaml uses module signatures (module type MONOID) and functor application (MonoidLaws(M)) to parameterise law verification over any monoid. Concrete instances (StringMonoid, ListMonoid, SumMonoid) are modules satisfying the signature, and composition is List.fold_left M.append M.empty.

Full Source

#![allow(clippy::all)]
// A monoid viewed as a single-object category:
//   - One object: ()
//   - Morphisms: the monoid elements
//   - Composition: monoid append (associative)
//   - Identity: monoid empty

/// Trait encoding the Monoid abstraction (and therefore a single-object category).
pub trait Monoid {
    fn empty() -> Self;
    fn append(self, other: Self) -> Self;
}

// ── Concrete monoid instances ────────────────────────────────────────────────

/// String monoid: identity = "", operation = concatenation
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct StringMonoid(pub String);

impl Monoid for StringMonoid {
    fn empty() -> Self {
        StringMonoid(String::new())
    }
    fn append(self, other: Self) -> Self {
        StringMonoid(self.0 + &other.0)
    }
}

/// Sum monoid: identity = 0, operation = addition
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SumMonoid(pub i64);

impl Monoid for SumMonoid {
    fn empty() -> Self {
        SumMonoid(0)
    }
    fn append(self, other: Self) -> Self {
        SumMonoid(self.0 + other.0)
    }
}

/// Product monoid: identity = 1, operation = multiplication
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ProductMonoid(pub i64);

impl Monoid for ProductMonoid {
    fn empty() -> Self {
        ProductMonoid(1)
    }
    fn append(self, other: Self) -> Self {
        ProductMonoid(self.0 * other.0)
    }
}

/// List (Vec) monoid: identity = [], operation = concatenation
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ListMonoid<T>(pub Vec<T>);

impl<T: Clone> Monoid for ListMonoid<T> {
    fn empty() -> Self {
        ListMonoid(Vec::new())
    }
    fn append(self, other: Self) -> Self {
        let mut v = self.0;
        v.extend(other.0);
        ListMonoid(v)
    }
}

// ── Monoid laws (as functions, not just assertions) ──────────────────────────

/// Left identity law: empty <> x == x
pub fn check_left_identity<M: Monoid + PartialEq + Clone>(x: M) -> bool {
    M::empty().append(x.clone()) == x
}

/// Right identity law: x <> empty == x
pub fn check_right_identity<M: Monoid + PartialEq + Clone>(x: M) -> bool {
    x.clone().append(M::empty()) == x
}

/// Associativity law: (x <> y) <> z == x <> (y <> z)
pub fn check_associativity<M: Monoid + PartialEq + Clone>(x: M, y: M, z: M) -> bool {
    x.clone().append(y.clone()).append(z.clone()) == x.append(y.append(z))
}

// ── Monoid as category: fold morphisms via composition ───────────────────────

/// Compose a sequence of morphisms (monoid elements) using fold_left —
/// mirrors `List.fold_left M.append M.empty ms` from OCaml.
pub fn compose_morphisms<M: Monoid>(morphisms: impl IntoIterator<Item = M>) -> M {
    morphisms
        .into_iter()
        .fold(M::empty(), |acc, m| acc.append(m))
}

// ── Recursive style (explicit fold) ─────────────────────────────────────────

/// Recursive version of compose_morphisms, closer to the OCaml recursive style.
pub fn compose_morphisms_recursive<M: Monoid + Clone>(morphisms: &[M]) -> M {
    match morphisms {
        [] => M::empty(),
        [x] => x.clone(),
        [head, rest @ ..] => head.clone().append(compose_morphisms_recursive(rest)),
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    // ── StringMonoid ──────────────────────────────────────────────────────────

    #[test]
    fn test_string_left_identity() {
        assert!(check_left_identity(StringMonoid("hello".into())));
    }

    #[test]
    fn test_string_right_identity() {
        assert!(check_right_identity(StringMonoid("hello".into())));
    }

    #[test]
    fn test_string_associativity() {
        assert!(check_associativity(
            StringMonoid("a".into()),
            StringMonoid("b".into()),
            StringMonoid("c".into()),
        ));
    }

    #[test]
    fn test_string_compose_morphisms() {
        let words = vec![
            StringMonoid("hello".into()),
            StringMonoid(", ".into()),
            StringMonoid("world".into()),
            StringMonoid("!".into()),
        ];
        assert_eq!(
            compose_morphisms(words),
            StringMonoid("hello, world!".into())
        );
    }

    #[test]
    fn test_string_compose_empty() {
        let empty: Vec<StringMonoid> = vec![];
        assert_eq!(compose_morphisms(empty), StringMonoid(String::new()));
    }

    // ── SumMonoid ─────────────────────────────────────────────────────────────

    #[test]
    fn test_sum_identity() {
        assert!(check_left_identity(SumMonoid(42)));
        assert!(check_right_identity(SumMonoid(42)));
    }

    #[test]
    fn test_sum_associativity() {
        assert!(check_associativity(
            SumMonoid(1),
            SumMonoid(2),
            SumMonoid(3)
        ));
    }

    #[test]
    fn test_sum_compose() {
        let ms = vec![SumMonoid(1), SumMonoid(2), SumMonoid(3), SumMonoid(4)];
        assert_eq!(compose_morphisms(ms), SumMonoid(10));
    }

    // ── ProductMonoid ─────────────────────────────────────────────────────────

    #[test]
    fn test_product_identity() {
        assert!(check_left_identity(ProductMonoid(5)));
        assert!(check_right_identity(ProductMonoid(5)));
    }

    #[test]
    fn test_product_associativity() {
        assert!(check_associativity(
            ProductMonoid(2),
            ProductMonoid(3),
            ProductMonoid(4)
        ));
    }

    #[test]
    fn test_product_compose() {
        let ms = vec![ProductMonoid(2), ProductMonoid(3), ProductMonoid(4)];
        assert_eq!(compose_morphisms(ms), ProductMonoid(24));
    }

    // ── ListMonoid ────────────────────────────────────────────────────────────

    #[test]
    fn test_list_identity() {
        assert!(check_left_identity(ListMonoid(vec![1, 2, 3])));
        assert!(check_right_identity(ListMonoid(vec![1, 2, 3])));
    }

    #[test]
    fn test_list_associativity() {
        assert!(check_associativity(
            ListMonoid(vec![1]),
            ListMonoid(vec![2]),
            ListMonoid(vec![3]),
        ));
    }

    #[test]
    fn test_list_compose() {
        let ms = vec![
            ListMonoid(vec![1, 2]),
            ListMonoid(vec![3, 4]),
            ListMonoid(vec![5]),
        ];
        assert_eq!(compose_morphisms(ms), ListMonoid(vec![1, 2, 3, 4, 5]));
    }

    // ── Recursive compose ─────────────────────────────────────────────────────

    #[test]
    fn test_recursive_compose_empty() {
        let ms: Vec<SumMonoid> = vec![];
        assert_eq!(compose_morphisms_recursive(&ms), SumMonoid(0));
    }

    #[test]
    fn test_recursive_compose_single() {
        assert_eq!(compose_morphisms_recursive(&[SumMonoid(7)]), SumMonoid(7));
    }

    #[test]
    fn test_recursive_compose_multiple() {
        let ms = vec![SumMonoid(1), SumMonoid(2), SumMonoid(3)];
        assert_eq!(compose_morphisms_recursive(&ms), SumMonoid(6));
    }

    #[test]
    fn test_recursive_string() {
        let words = vec![
            StringMonoid("foo".into()),
            StringMonoid("bar".into()),
            StringMonoid("baz".into()),
        ];
        assert_eq!(
            compose_morphisms_recursive(&words),
            StringMonoid("foobarbaz".into())
        );
    }
}

(* A monoid viewed as a single-object category:
   - One object: ()
   - Morphisms: the monoid elements
   - Composition: monoid append (associative)
   - Identity: monoid empty *)

module type MONOID = sig
  type t
  val empty  : t
  val append : t -> t -> t
end

(* Verify monoid laws *)
module MonoidLaws (M : MONOID) = struct
  let check_identity x =
    M.append M.empty x = x &&
    M.append x M.empty = x

  let check_associativity x y z =
    M.append (M.append x y) z = M.append x (M.append y z)
end

(* String monoid *)
module StringMonoid : MONOID with type t = string = struct
  type t = string
  let empty  = ""
  let append = ( ^ )
end

(* List monoid *)
module ListMonoid : MONOID with type t = int list = struct
  type t = int list
  let empty  = []
  let append = ( @ )
end

(* Sum monoid *)
module SumMonoid : MONOID with type t = int = struct
  type t = int
  let empty  = 0
  let append = ( + )
end

let () =
  let module SL = MonoidLaws (StringMonoid) in
  let module LL = MonoidLaws (ListMonoid) in
  let module NL = MonoidLaws (SumMonoid) in

  assert (SL.check_identity "hello");
  assert (SL.check_associativity "a" "b" "c");
  assert (LL.check_identity [1;2;3]);
  assert (NL.check_identity 42);

  Printf.printf "All monoid laws verified\n";

  (* Monoid as category: compose morphisms *)
  let compose_morphisms ms =
    List.fold_left StringMonoid.append StringMonoid.empty ms
  in
  Printf.printf "Composed: %s\n" (compose_morphisms ["hello"; ", "; "world"; "!"])

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    // ── StringMonoid ──────────────────────────────────────────────────────────

    #[test]
    fn test_string_left_identity() {
        assert!(check_left_identity(StringMonoid("hello".into())));
    }

    #[test]
    fn test_string_right_identity() {
        assert!(check_right_identity(StringMonoid("hello".into())));
    }

    #[test]
    fn test_string_associativity() {
        assert!(check_associativity(
            StringMonoid("a".into()),
            StringMonoid("b".into()),
            StringMonoid("c".into()),
        ));
    }

    #[test]
    fn test_string_compose_morphisms() {
        let words = vec![
            StringMonoid("hello".into()),
            StringMonoid(", ".into()),
            StringMonoid("world".into()),
            StringMonoid("!".into()),
        ];
        assert_eq!(
            compose_morphisms(words),
            StringMonoid("hello, world!".into())
        );
    }

    #[test]
    fn test_string_compose_empty() {
        let empty: Vec<StringMonoid> = vec![];
        assert_eq!(compose_morphisms(empty), StringMonoid(String::new()));
    }

    // ── SumMonoid ─────────────────────────────────────────────────────────────

    #[test]
    fn test_sum_identity() {
        assert!(check_left_identity(SumMonoid(42)));
        assert!(check_right_identity(SumMonoid(42)));
    }

    #[test]
    fn test_sum_associativity() {
        assert!(check_associativity(
            SumMonoid(1),
            SumMonoid(2),
            SumMonoid(3)
        ));
    }

    #[test]
    fn test_sum_compose() {
        let ms = vec![SumMonoid(1), SumMonoid(2), SumMonoid(3), SumMonoid(4)];
        assert_eq!(compose_morphisms(ms), SumMonoid(10));
    }

    // ── ProductMonoid ─────────────────────────────────────────────────────────

    #[test]
    fn test_product_identity() {
        assert!(check_left_identity(ProductMonoid(5)));
        assert!(check_right_identity(ProductMonoid(5)));
    }

    #[test]
    fn test_product_associativity() {
        assert!(check_associativity(
            ProductMonoid(2),
            ProductMonoid(3),
            ProductMonoid(4)
        ));
    }

    #[test]
    fn test_product_compose() {
        let ms = vec![ProductMonoid(2), ProductMonoid(3), ProductMonoid(4)];
        assert_eq!(compose_morphisms(ms), ProductMonoid(24));
    }

    // ── ListMonoid ────────────────────────────────────────────────────────────

    #[test]
    fn test_list_identity() {
        assert!(check_left_identity(ListMonoid(vec![1, 2, 3])));
        assert!(check_right_identity(ListMonoid(vec![1, 2, 3])));
    }

    #[test]
    fn test_list_associativity() {
        assert!(check_associativity(
            ListMonoid(vec![1]),
            ListMonoid(vec![2]),
            ListMonoid(vec![3]),
        ));
    }

    #[test]
    fn test_list_compose() {
        let ms = vec![
            ListMonoid(vec![1, 2]),
            ListMonoid(vec![3, 4]),
            ListMonoid(vec![5]),
        ];
        assert_eq!(compose_morphisms(ms), ListMonoid(vec![1, 2, 3, 4, 5]));
    }

    // ── Recursive compose ─────────────────────────────────────────────────────

    #[test]
    fn test_recursive_compose_empty() {
        let ms: Vec<SumMonoid> = vec![];
        assert_eq!(compose_morphisms_recursive(&ms), SumMonoid(0));
    }

    #[test]
    fn test_recursive_compose_single() {
        assert_eq!(compose_morphisms_recursive(&[SumMonoid(7)]), SumMonoid(7));
    }

    #[test]
    fn test_recursive_compose_multiple() {
        let ms = vec![SumMonoid(1), SumMonoid(2), SumMonoid(3)];
        assert_eq!(compose_morphisms_recursive(&ms), SumMonoid(6));
    }

    #[test]
    fn test_recursive_string() {
        let words = vec![
            StringMonoid("foo".into()),
            StringMonoid("bar".into()),
            StringMonoid("baz".into()),
        ];
        assert_eq!(
            compose_morphisms_recursive(&words),
            StringMonoid("foobarbaz".into())
        );
    }
}

Deep Comparison

OCaml vs Rust: Monoid as a Category

Side-by-Side Code

OCaml

module type MONOID = sig
  type t
  val empty  : t
  val append : t -> t -> t
end

module MonoidLaws (M : MONOID) = struct
  let check_identity x =
    M.append M.empty x = x &&
    M.append x M.empty = x

  let check_associativity x y z =
    M.append (M.append x y) z = M.append x (M.append y z)
end

module StringMonoid : MONOID with type t = string = struct
  type t = string
  let empty  = ""
  let append = ( ^ )
end

let compose_morphisms ms =
  List.fold_left StringMonoid.append StringMonoid.empty ms

Rust (idiomatic)

pub trait Monoid {
    fn empty() -> Self;
    fn append(self, other: Self) -> Self;
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct StringMonoid(pub String);

impl Monoid for StringMonoid {
    fn empty() -> Self { StringMonoid(String::new()) }
    fn append(self, other: Self) -> Self { StringMonoid(self.0 + &other.0) }
}

pub fn compose_morphisms<M: Monoid>(morphisms: impl IntoIterator<Item = M>) -> M {
    morphisms.into_iter().fold(M::empty(), |acc, m| acc.append(m))
}

Rust (functional/recursive)

pub fn compose_morphisms_recursive<M: Monoid + Clone>(morphisms: &[M]) -> M {
    match morphisms {
        []             => M::empty(),
        [x]            => x.clone(),
        [head, rest @ ..] => head.clone().append(compose_morphisms_recursive(rest)),
    }
}

Type Signatures

Concept	OCaml	Rust
Monoid abstraction	`module type MONOID`	`trait Monoid`
Identity element	`val empty : t`	`fn empty() -> Self`
Binary operation	`val append : t -> t -> t`	`fn append(self, other: Self) -> Self`
Law checker	`module MonoidLaws(M : MONOID)`	`fn check_identity<M: Monoid + PartialEq + Clone>(x: M) -> bool`
Fold morphisms	`List.fold_left M.append M.empty ms`	`iter.fold(M::empty(), \\|acc, m\\| acc.append(m))`
Multiple instances	Separate named modules	Newtypes + separate `impl` blocks

Key Insights

Modules vs traits: OCaml's first-class module system lets you pass monoid implementations as functor arguments; Rust achieves the same via trait bounds on generic functions.

Newtype pattern: Because Rust allows only one impl Trait for Type, newtypes (SumMonoid, ProductMonoid) let you give the same underlying type (e.g. i64) multiple distinct monoid structures without conflicting impl blocks.

**empty as a method:** OCaml's module value empty : t becomes a static method fn empty() -> Self in Rust — this is the idiomatic way to express a type-level constant in a trait.

**Ownership and append:** Rust's append(self, other: Self) -> Self consumes both values, mirroring OCaml's value semantics; references are unnecessary here because monoids typically build new values.

Fold = categorical composition: Both languages express the composition of a sequence of morphisms as a left fold with the identity as the initial accumulator — this is the direct computational realisation of the category axioms.

When to Use Each Style

Use idiomatic Rust (iterator fold) when: you have a collection of monoid values to reduce at runtime and want clean, allocation-free iteration. Use recursive Rust when: you want to make the structural recursion explicit and mirror the OCaml proof-style reasoning about the base and inductive cases of list composition.

Exercises

Show that any type with a Monoid instance induces a category with a single object by implementing the Category trait where morphisms are monoid elements and composition is the monoid operation.

Implement the free monoid on a type T (i.e., Vec<T>) and demonstrate the universal property: any function T -> M (where M is a monoid) extends uniquely to a monoid homomorphism Vec<T> -> M.

Define a Monoid instance for endomorphisms T -> T (composition as operation, identity function as unit) and use it to build a pipeline of string transformations via mconcat.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust