1098 Advanced

Monoid Pattern — Generic Combining

Type ClassesAlgebraic Abstractions

Tutorial Video

Text description (accessibility)

This video demonstrates the "Monoid Pattern — Generic Combining" functional Rust example. Difficulty level: Advanced. Key concepts covered: Type Classes, Algebraic Abstractions. Implement the monoid pattern: define a trait/module type with an identity element and an associative binary operation, then write a single generic `concat_all` function that folds any list using any monoid instance (sum, product, string concatenation, boolean AND/OR). Key difference from OCaml: 1. **Abstraction mechanism:** OCaml uses first

Tutorial

The Problem

Implement the monoid pattern: define a trait/module type with an identity element and an associative binary operation, then write a single generic concat_all function that folds any list using any monoid instance (sum, product, string concatenation, boolean AND/OR).

🎯 Learning Outcomes

• How Rust traits model OCaml's first-class module types for algebraic abstractions

• Using Iterator::fold as the idiomatic Rust parallel to List.fold_left

• Newtype wrappers (Sum(i64), Product(i64)) to give the same underlying type different monoid behavior

• The difference between OCaml's first-class modules (value-level) and Rust's trait-based dispatch (type-level)

🦀 The Rust Way

Rust uses a Monoid trait with empty() and combine() methods. Since Rust's trait system is type-level (not value-level), we use newtype wrappers (Sum, Product, Concat, All, Any) to distinguish different monoid behaviors for the same underlying type. The generic function concat_all<M: Monoid> uses the trait bound to dispatch statically at compile time.

Code Example

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

pub fn concat_all<M: Monoid>(items: impl IntoIterator<Item = M>) -> M {
    items.into_iter().fold(M::empty(), M::combine)
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Sum(pub i64);

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

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Product(pub i64);

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

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

let concat_all (type a) (module M : MONOID with type t = a) (lst : a list) =
  List.fold_left M.combine M.empty lst

module Sum = struct type t = int let empty = 0 let combine = (+) end
module Product = struct type t = int let empty = 1 let combine = ( * ) end

let () =
  Printf.printf "sum: %d\n" (concat_all (module Sum) [1;2;3;4;5]);
  Printf.printf "product: %d\n" (concat_all (module Product) [1;2;3;4;5])

Key Differences

Abstraction mechanism: OCaml uses first-class modules (value-level polymorphism); Rust uses traits (type-level polymorphism resolved at compile time via monomorphization).

Same-type disambiguation: OCaml can have multiple modules with type t = int; Rust needs newtype wrappers (Sum(i64) vs Product(i64)) because a type can only implement a trait once.

Folding: OCaml's List.fold_left takes a function and initial value; Rust's Iterator::fold is identical in spirit but works on any iterator, not just lists.

Identity resolution: OCaml's M.empty is a module field access; Rust's M::empty() is an associated function call resolved through the trait.

OCaml Approach

OCaml uses a module type MONOID signature and first-class modules. The concat_all function takes a packed module (module M : MONOID with type t = a) as a value argument, allowing the caller to pass different monoid implementations at runtime. Modules are true first-class values — you can store them in data structures, pass them to functions, and pattern-match on them.

Full Source

#![allow(clippy::all)]
/// A monoid is a type with an associative binary operation and an identity element.
///
/// This mirrors OCaml's `module type MONOID = sig type t val empty : t val combine : t -> t -> t end`
/// using Rust's trait system instead of first-class modules.
pub trait Monoid {
    fn empty() -> Self;
    fn combine(self, other: Self) -> Self;
}

// --- Solution 1: Idiomatic Rust — iterator fold with trait bound ---
// Uses Iterator::fold, the direct analogue of OCaml's List.fold_left
pub fn concat_all<M: Monoid>(items: impl IntoIterator<Item = M>) -> M {
    items.into_iter().fold(M::empty(), M::combine)
}

// --- Solution 2: Recursive — closer to OCaml's fold_left unrolled ---
// Explicit recursion over a slice, mirroring OCaml pattern matching on lists.
// Requires Clone because we need to produce owned values from references.
pub fn concat_all_recursive<M: Monoid + Clone>(items: &[M]) -> M {
    match items {
        [] => M::empty(),
        [x] => x.clone(),
        [x, rest @ ..] => M::combine(x.clone(), concat_all_recursive(rest)),
    }
}

// --- Solution 3: reduce-based — avoids calling empty() when list is non-empty ---
// Uses Iterator::reduce, returning None for empty iterators.
pub fn concat_all_reduce<M: Monoid>(items: impl IntoIterator<Item = M>) -> Option<M> {
    items.into_iter().reduce(M::combine)
}

// --- Monoid instances ---

/// Additive monoid over i64 (identity: 0, operation: +)
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Sum(pub i64);

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

/// Multiplicative monoid over i64 (identity: 1, operation: *)
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Product(pub i64);

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

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

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

/// Boolean AND monoid (identity: true, operation: &&)
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct All(pub bool);

impl Monoid for All {
    fn empty() -> Self {
        All(true)
    }
    fn combine(self, other: Self) -> Self {
        All(self.0 && other.0)
    }
}

/// Boolean OR monoid (identity: false, operation: ||)
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Any(pub bool);

impl Monoid for Any {
    fn empty() -> Self {
        Any(false)
    }
    fn combine(self, other: Self) -> Self {
        Any(self.0 || other.0)
    }
}

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

    // --- Sum tests ---

    #[test]
    fn sum_empty_list() {
        assert_eq!(concat_all::<Sum>(vec![]), Sum(0));
    }

    #[test]
    fn sum_single_element() {
        assert_eq!(concat_all(vec![Sum(42)]), Sum(42));
    }

    #[test]
    fn sum_multiple_elements() {
        assert_eq!(
            concat_all(vec![Sum(1), Sum(2), Sum(3), Sum(4), Sum(5)]),
            Sum(15)
        );
    }

    #[test]
    fn sum_with_negatives() {
        assert_eq!(concat_all(vec![Sum(-1), Sum(2), Sum(-3)]), Sum(-2));
    }

    // --- Product tests ---

    #[test]
    fn product_empty_list() {
        assert_eq!(concat_all::<Product>(vec![]), Product(1));
    }

    #[test]
    fn product_single_element() {
        assert_eq!(concat_all(vec![Product(7)]), Product(7));
    }

    #[test]
    fn product_multiple_elements() {
        assert_eq!(
            concat_all(vec![
                Product(1),
                Product(2),
                Product(3),
                Product(4),
                Product(5)
            ]),
            Product(120)
        );
    }

    #[test]
    fn product_with_zero() {
        assert_eq!(
            concat_all(vec![Product(5), Product(0), Product(3)]),
            Product(0)
        );
    }

    // --- Concat tests ---

    #[test]
    fn concat_empty_list() {
        assert_eq!(concat_all::<Concat>(vec![]), Concat(String::new()));
    }

    #[test]
    fn concat_single_element() {
        assert_eq!(
            concat_all(vec![Concat("hello".into())]),
            Concat("hello".into())
        );
    }

    #[test]
    fn concat_multiple_elements() {
        assert_eq!(
            concat_all(vec![
                Concat("hello".into()),
                Concat(" ".into()),
                Concat("world".into())
            ]),
            Concat("hello world".into())
        );
    }

    // --- All (boolean AND) tests ---

    #[test]
    fn all_empty_list() {
        assert_eq!(concat_all::<All>(vec![]), All(true));
    }

    #[test]
    fn all_true_elements() {
        assert_eq!(concat_all(vec![All(true), All(true), All(true)]), All(true));
    }

    #[test]
    fn all_with_false() {
        assert_eq!(
            concat_all(vec![All(true), All(true), All(false)]),
            All(false)
        );
    }

    // --- Any (boolean OR) tests ---

    #[test]
    fn any_empty_list() {
        assert_eq!(concat_all::<Any>(vec![]), Any(false));
    }

    #[test]
    fn any_all_false() {
        assert_eq!(concat_all(vec![Any(false), Any(false)]), Any(false));
    }

    #[test]
    fn any_with_true() {
        assert_eq!(
            concat_all(vec![Any(false), Any(true), Any(false)]),
            Any(true)
        );
    }

    // --- Recursive variant tests ---

    #[test]
    fn recursive_sum_empty() {
        assert_eq!(concat_all_recursive::<Sum>(&[]), Sum(0));
    }

    #[test]
    fn recursive_sum_multiple() {
        assert_eq!(
            concat_all_recursive(&[Sum(1), Sum(2), Sum(3), Sum(4), Sum(5)]),
            Sum(15)
        );
    }

    #[test]
    fn recursive_concat_multiple() {
        assert_eq!(
            concat_all_recursive(&[
                Concat("hello".into()),
                Concat(" ".into()),
                Concat("world".into())
            ]),
            Concat("hello world".into())
        );
    }

    // --- Reduce variant tests ---

    #[test]
    fn reduce_empty_returns_none() {
        assert_eq!(concat_all_reduce::<Sum>(vec![]), None);
    }

    #[test]
    fn reduce_nonempty_returns_some() {
        assert_eq!(
            concat_all_reduce(vec![Sum(1), Sum(2), Sum(3)]),
            Some(Sum(6))
        );
    }

    // --- Monoid law tests ---

    #[test]
    fn sum_identity_law() {
        // combine(empty, x) == x and combine(x, empty) == x
        let x = Sum(42);
        assert_eq!(Sum::combine(Sum::empty(), x), x);
        assert_eq!(Sum::combine(x, Sum::empty()), x);
    }

    #[test]
    fn sum_associativity_law() {
        // combine(combine(a, b), c) == combine(a, combine(b, c))
        let (a, b, c) = (Sum(1), Sum(2), Sum(3));
        assert_eq!(
            Sum::combine(Sum::combine(a, b), c),
            Sum::combine(a, Sum::combine(b, c))
        );
    }

    #[test]
    fn product_identity_law() {
        let x = Product(42);
        assert_eq!(Product::combine(Product::empty(), x), x);
        assert_eq!(Product::combine(x, Product::empty()), x);
    }

    #[test]
    fn product_associativity_law() {
        let (a, b, c) = (Product(2), Product(3), Product(4));
        assert_eq!(
            Product::combine(Product::combine(a, b), c),
            Product::combine(a, Product::combine(b, c))
        );
    }
}

(* Example 1098: Monoid Pattern — Generic Combining *)
(* A monoid has an identity element (empty) and an associative binary operation (combine). *)

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

(* concat_all: fold a list using any monoid — first-class module as argument *)
let concat_all (type a) (module M : MONOID with type t = a) (lst : a list) =
  List.fold_left M.combine M.empty lst

(* Concrete monoid modules *)
module Sum = struct type t = int let empty = 0 let combine = (+) end
module Product = struct type t = int let empty = 1 let combine = ( * ) end
module Concat = struct type t = string let empty = "" let combine = (^) end
module All = struct type t = bool let empty = true let combine = (&&) end
module Any = struct type t = bool let empty = false let combine = (||) end

(* Tests *)
let () =
  (* Sum monoid *)
  assert (concat_all (module Sum) [1;2;3;4;5] = 15);
  assert (concat_all (module Sum) [] = 0);
  assert (concat_all (module Sum) [42] = 42);

  (* Product monoid *)
  assert (concat_all (module Product) [1;2;3;4;5] = 120);
  assert (concat_all (module Product) [] = 1);
  assert (concat_all (module Product) [5;0;3] = 0);

  (* Concat monoid *)
  assert (concat_all (module Concat) ["hello";" ";"world"] = "hello world");
  assert (concat_all (module Concat) [] = "");

  (* All (boolean AND) monoid *)
  assert (concat_all (module All) [true; true; true] = true);
  assert (concat_all (module All) [true; true; false] = false);
  assert (concat_all (module All) [] = true);

  (* Any (boolean OR) monoid *)
  assert (concat_all (module Any) [false; false] = false);
  assert (concat_all (module Any) [false; true; false] = true);
  assert (concat_all (module Any) [] = false);

  print_endline "ok"

✓ Tests Rust test suite

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

    // --- Sum tests ---

    #[test]
    fn sum_empty_list() {
        assert_eq!(concat_all::<Sum>(vec![]), Sum(0));
    }

    #[test]
    fn sum_single_element() {
        assert_eq!(concat_all(vec![Sum(42)]), Sum(42));
    }

    #[test]
    fn sum_multiple_elements() {
        assert_eq!(
            concat_all(vec![Sum(1), Sum(2), Sum(3), Sum(4), Sum(5)]),
            Sum(15)
        );
    }

    #[test]
    fn sum_with_negatives() {
        assert_eq!(concat_all(vec![Sum(-1), Sum(2), Sum(-3)]), Sum(-2));
    }

    // --- Product tests ---

    #[test]
    fn product_empty_list() {
        assert_eq!(concat_all::<Product>(vec![]), Product(1));
    }

    #[test]
    fn product_single_element() {
        assert_eq!(concat_all(vec![Product(7)]), Product(7));
    }

    #[test]
    fn product_multiple_elements() {
        assert_eq!(
            concat_all(vec![
                Product(1),
                Product(2),
                Product(3),
                Product(4),
                Product(5)
            ]),
            Product(120)
        );
    }

    #[test]
    fn product_with_zero() {
        assert_eq!(
            concat_all(vec![Product(5), Product(0), Product(3)]),
            Product(0)
        );
    }

    // --- Concat tests ---

    #[test]
    fn concat_empty_list() {
        assert_eq!(concat_all::<Concat>(vec![]), Concat(String::new()));
    }

    #[test]
    fn concat_single_element() {
        assert_eq!(
            concat_all(vec![Concat("hello".into())]),
            Concat("hello".into())
        );
    }

    #[test]
    fn concat_multiple_elements() {
        assert_eq!(
            concat_all(vec![
                Concat("hello".into()),
                Concat(" ".into()),
                Concat("world".into())
            ]),
            Concat("hello world".into())
        );
    }

    // --- All (boolean AND) tests ---

    #[test]
    fn all_empty_list() {
        assert_eq!(concat_all::<All>(vec![]), All(true));
    }

    #[test]
    fn all_true_elements() {
        assert_eq!(concat_all(vec![All(true), All(true), All(true)]), All(true));
    }

    #[test]
    fn all_with_false() {
        assert_eq!(
            concat_all(vec![All(true), All(true), All(false)]),
            All(false)
        );
    }

    // --- Any (boolean OR) tests ---

    #[test]
    fn any_empty_list() {
        assert_eq!(concat_all::<Any>(vec![]), Any(false));
    }

    #[test]
    fn any_all_false() {
        assert_eq!(concat_all(vec![Any(false), Any(false)]), Any(false));
    }

    #[test]
    fn any_with_true() {
        assert_eq!(
            concat_all(vec![Any(false), Any(true), Any(false)]),
            Any(true)
        );
    }

    // --- Recursive variant tests ---

    #[test]
    fn recursive_sum_empty() {
        assert_eq!(concat_all_recursive::<Sum>(&[]), Sum(0));
    }

    #[test]
    fn recursive_sum_multiple() {
        assert_eq!(
            concat_all_recursive(&[Sum(1), Sum(2), Sum(3), Sum(4), Sum(5)]),
            Sum(15)
        );
    }

    #[test]
    fn recursive_concat_multiple() {
        assert_eq!(
            concat_all_recursive(&[
                Concat("hello".into()),
                Concat(" ".into()),
                Concat("world".into())
            ]),
            Concat("hello world".into())
        );
    }

    // --- Reduce variant tests ---

    #[test]
    fn reduce_empty_returns_none() {
        assert_eq!(concat_all_reduce::<Sum>(vec![]), None);
    }

    #[test]
    fn reduce_nonempty_returns_some() {
        assert_eq!(
            concat_all_reduce(vec![Sum(1), Sum(2), Sum(3)]),
            Some(Sum(6))
        );
    }

    // --- Monoid law tests ---

    #[test]
    fn sum_identity_law() {
        // combine(empty, x) == x and combine(x, empty) == x
        let x = Sum(42);
        assert_eq!(Sum::combine(Sum::empty(), x), x);
        assert_eq!(Sum::combine(x, Sum::empty()), x);
    }

    #[test]
    fn sum_associativity_law() {
        // combine(combine(a, b), c) == combine(a, combine(b, c))
        let (a, b, c) = (Sum(1), Sum(2), Sum(3));
        assert_eq!(
            Sum::combine(Sum::combine(a, b), c),
            Sum::combine(a, Sum::combine(b, c))
        );
    }

    #[test]
    fn product_identity_law() {
        let x = Product(42);
        assert_eq!(Product::combine(Product::empty(), x), x);
        assert_eq!(Product::combine(x, Product::empty()), x);
    }

    #[test]
    fn product_associativity_law() {
        let (a, b, c) = (Product(2), Product(3), Product(4));
        assert_eq!(
            Product::combine(Product::combine(a, b), c),
            Product::combine(a, Product::combine(b, c))
        );
    }
}

Deep Comparison

OCaml vs Rust: Monoid Pattern — Generic Combining

Side-by-Side Code

OCaml

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

let concat_all (type a) (module M : MONOID with type t = a) (lst : a list) =
  List.fold_left M.combine M.empty lst

module Sum = struct type t = int let empty = 0 let combine = (+) end
module Product = struct type t = int let empty = 1 let combine = ( * ) end

let () =
  Printf.printf "sum: %d\n" (concat_all (module Sum) [1;2;3;4;5]);
  Printf.printf "product: %d\n" (concat_all (module Product) [1;2;3;4;5])

Rust (idiomatic)

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

pub fn concat_all<M: Monoid>(items: impl IntoIterator<Item = M>) -> M {
    items.into_iter().fold(M::empty(), M::combine)
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Sum(pub i64);

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

#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Product(pub i64);

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

Rust (recursive)

pub fn concat_all_recursive<M: Monoid + Clone>(items: &[M]) -> M {
    match items {
        [] => M::empty(),
        [x] => x.clone(),
        [x, rest @ ..] => M::combine(x.clone(), concat_all_recursive(rest)),
    }
}

Type Signatures

Concept	OCaml	Rust
Module type / Trait	`module type MONOID = sig type t val empty : t val combine : t -> t -> t end`	`trait Monoid { fn empty() -> Self; fn combine(self, other: Self) -> Self; }`
Generic fold function	`val concat_all : (module MONOID with type t = 'a) -> 'a list -> 'a`	`fn concat_all<M: Monoid>(items: impl IntoIterator<Item = M>) -> M`
Identity element	`M.empty` (module field)	`M::empty()` (associated function)
Binary operation	`M.combine` (module field, curried)	`M::combine` (method, two args)
Newtype for int	Not needed — modules disambiguate	`struct Sum(pub i64)` / `struct Product(pub i64)`

Key Insights

First-class modules vs traits: OCaml's first-class modules are value-level — you pass (module Sum) as a runtime argument. Rust's traits are type-level — M: Monoid is resolved at compile time via monomorphization. Both achieve the same abstraction, but OCaml's is more dynamic and Rust's is zero-cost.

Newtype pattern is essential in Rust: OCaml can define Sum and Product both with type t = int because modules are distinct values. In Rust, i64 can only implement Monoid once, so we wrap it in newtypes (Sum(i64), Product(i64)) to create distinct types with distinct trait implementations.

Currying vs explicit arguments: OCaml's combine = (+) is naturally curried — (+) is already int -> int -> int. Rust's combine(self, other: Self) takes two explicit arguments. The fold call adapts naturally: OCaml's List.fold_left M.combine M.empty lst becomes Rust's items.into_iter().fold(M::empty(), M::combine).

Iterator generality: OCaml's concat_all takes 'a list. Rust's version takes impl IntoIterator<Item = M>, making it work with any iterator — vectors, arrays, ranges, or lazy chains — not just lists.

Clone requirement in recursive version: The recursive Rust version needs Clone because it works with &[M] (borrowed slice) but must produce an owned M. OCaml's garbage collector handles this transparently — values are reference-counted, so "copying" is just bumping a counter.

When to Use Each Style

Use idiomatic Rust (fold) when: You want the standard, efficient approach. The fold version works with any iterator, avoids Clone bounds, and is the natural Rust way to express monoidal aggregation. This is the default choice.

Use recursive Rust when: You're teaching the OCaml-to-Rust translation pattern, or when the combining logic has complex branching that doesn't map cleanly to a single fold. The recursive version also demonstrates slice pattern matching ([x, rest @ ..]), which is a powerful Rust feature for list-like processing.

Exercises

Add a First<T> newtype monoid that always returns its left operand (identity = None) and a Last<T> that returns the right operand, and use them to find the first and last element of a list with concat_all.

Implement the Endo monoid whose elements are functions T -> T and whose binary operation is composition, then use concat_all to compose a list of string transformations.

Implement a Validated applicative using the monoid pattern: accumulate all validation errors (rather than short-circuiting) by combining Vec<String> error lists.

Open Source Repos

functional-rust

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

Rust