1084 Intermediate

Monoid Pattern

Functional Programming

Tutorial

The Problem

A monoid is an algebraic structure consisting of a type, an associative binary operation, and an identity element for that operation. This example demonstrates how to express the monoid abstraction in both OCaml and Rust, implement two concrete instances (additive integers and multiplicative integers), and write a single generic reduce function that collapses any collection of monoid values into one — with correct behavior on empty inputs without special-casing. The pattern appears throughout real codebases: string concatenation, list merging, statistics accumulation, and parallel map-reduce all rest on monoid laws.

🎯 Learning Outcomes

• What the three monoid laws are (closure, associativity, identity) and how they guarantee safe generic reduction

• How OCaml's first-class modules (module type MONOID) and Rust's traits encode the same abstraction through different mechanisms

• Why Rust requires newtype wrappers (Sum, Product) to provide two distinct Monoid implementations for the same underlying i32 type

• How fold with a monoid identity eliminates the empty-collection edge case that plagues naive reduce implementations

• How the T: Clone bound in reduce_monoid relates to the cloned() iterator adapter and when it can be avoided

Code Example

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

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

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

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

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

pub fn reduce_monoid<T: Monoid + Clone>(items: &[T]) -> T {
    items.iter().cloned().fold(T::empty(), |acc, x| acc.combine(x))
}

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

module Sum : MONOID with type t = int = struct
  type t = int
  let empty = 0
  let combine x y = x + y
end

module Product : MONOID with type t = int = struct
  type t = int
  let empty = 1
  let combine x y = x * y
end

(* Generic reduce using first-class modules *)
let reduce (type a) (module M : MONOID with type t = a) lst =
  List.fold_left M.combine M.empty lst

let () =
  assert (reduce (module Sum)     [1;2;3;4;5] = 15);
  assert (reduce (module Product) [1;2;3;4;5] = 120)

Key Differences

Abstraction mechanism: OCaml passes implementations as first-class modules at the call site; Rust selects implementations statically through trait bounds, resolved at compile time via monomorphization

Type disambiguation: OCaml places two int-backed implementations in separate module namespaces (Sum.combine, Product.combine); Rust needs distinct newtype wrappers to implement the same trait for the same base type

Identity element: OCaml expresses empty as a module-level value binding val empty : t; Rust requires an associated function fn empty() -> Self because trait items cannot be constants without const trait support

Reduction function: OCaml's reduce takes a first-class module argument making the monoid explicit at each call site; Rust's reduce_monoid infers the monoid from the element type, which is more concise but less flexible when multiple implementations exist for a type

OCaml Approach

OCaml defines a MONOID module signature with three members: type t, val empty : t, and val combine : t -> t -> t. Sum and Product are separate modules satisfying this signature, both using int as the underlying type — there is no naming conflict because module namespaces keep them distinct. The generic reduce function uses a locally abstract type (let reduce (type a) (module M : MONOID with type t = a)) to accept any first-class module at the call site and then folds with List.fold_left M.combine M.empty. This is idiomatic OCaml functor-in-miniature style.

Full Source

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

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

impl Monoid for Sum {
    fn empty() -> Self {
        Sum(0)
    }

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

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

impl Monoid for Product {
    fn empty() -> Self {
        Product(1)
    }

    fn combine(self, other: Self) -> Self {
        Product(self.0 * other.0)
    }
}

pub fn reduce_monoid<T: Monoid + Clone>(items: &[T]) -> T {
    items
        .iter()
        .cloned()
        .fold(T::empty(), |acc, x| acc.combine(x))
}

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

    #[test]
    fn test_sum_monoid() {
        let nums = vec![Sum(1), Sum(2), Sum(3)];
        assert_eq!(reduce_monoid(&nums), Sum(6));
        assert_eq!(Sum::empty().combine(Sum(5)), Sum(5));
    }

    #[test]
    fn test_product_monoid() {
        let nums = vec![Product(1), Product(2), Product(3)];
        assert_eq!(reduce_monoid(&nums), Product(6));
        assert_eq!(Product::empty().combine(Product(5)), Product(5));
    }

    #[test]
    fn test_empty_sum() {
        let nums: Vec<Sum> = vec![];
        assert_eq!(reduce_monoid(&nums), Sum(0));
    }

    #[test]
    fn test_empty_product() {
        let nums: Vec<Product> = vec![];
        assert_eq!(reduce_monoid(&nums), Product(1));
    }
}

(* OCaml implementation of the Monoid pattern *)
(* A monoid consists of a type, an associative binary operation, and an identity element. *)

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

(* Sum Monoid *)
module Sum : MONOID with type t = int = struct
  type t = int
  let empty = 0
  let combine x y = x + y
end

(* Product Monoid *)
module Product : MONOID with type t = int = struct
  type t = int
  let empty = 1
  let combine x y = x * y
end

(* List reduction function using a Monoid *)
let reduce (type a) (module M : MONOID with type t = a) (lst : a list) : a = 
  List.fold_left M.combine M.empty lst

(* Test cases (using standard OCaml interactive top-level syntax for demonstration) *)
let () = 
  print_endline "--- Sum Monoid ---";
  let sum_list = [1; 2; 3; 4; 5] in
  let total_sum = reduce (module Sum) sum_list in
  Printf.printf "Sum of [1;2;3;4;5] is: %d\n" total_sum; (* Expected: 15 *)
  assert (total_sum = 15);

  let empty_sum = reduce (module Sum) [] in
  Printf.printf "Sum of [] is: %d\n" empty_sum; (* Expected: 0 *)
  assert (empty_sum = 0);

  print_endline "\n--- Product Monoid ---";
  let product_list = [1; 2; 3; 4; 5] in
  let total_product = reduce (module Product) product_list in
  Printf.printf "Product of [1;2;3;4;5] is: %d\n" total_product; (* Expected: 120 *)
  assert (total_product = 120);

  let empty_product = reduce (module Product) [] in
  Printf.printf "Product of [] is: %d\n" empty_product; (* Expected: 1 *)
  assert (empty_product = 1);

  print_endline "All Monoid tests passed!"

✓ Tests Rust test suite

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

    #[test]
    fn test_sum_monoid() {
        let nums = vec![Sum(1), Sum(2), Sum(3)];
        assert_eq!(reduce_monoid(&nums), Sum(6));
        assert_eq!(Sum::empty().combine(Sum(5)), Sum(5));
    }

    #[test]
    fn test_product_monoid() {
        let nums = vec![Product(1), Product(2), Product(3)];
        assert_eq!(reduce_monoid(&nums), Product(6));
        assert_eq!(Product::empty().combine(Product(5)), Product(5));
    }

    #[test]
    fn test_empty_sum() {
        let nums: Vec<Sum> = vec![];
        assert_eq!(reduce_monoid(&nums), Sum(0));
    }

    #[test]
    fn test_empty_product() {
        let nums: Vec<Product> = vec![];
        assert_eq!(reduce_monoid(&nums), Product(1));
    }
}

Deep Comparison

OCaml vs Rust: Monoid Pattern

Side-by-Side Code

OCaml

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

module Sum : MONOID with type t = int = struct
  type t = int
  let empty = 0
  let combine x y = x + y
end

module Product : MONOID with type t = int = struct
  type t = int
  let empty = 1
  let combine x y = x * y
end

(* Generic reduce using first-class modules *)
let reduce (type a) (module M : MONOID with type t = a) lst =
  List.fold_left M.combine M.empty lst

let () =
  assert (reduce (module Sum)     [1;2;3;4;5] = 15);
  assert (reduce (module Product) [1;2;3;4;5] = 120)

Rust (idiomatic)

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

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

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

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

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

pub fn reduce_monoid<T: Monoid + Clone>(items: &[T]) -> T {
    items.iter().cloned().fold(T::empty(), |acc, x| acc.combine(x))
}

Rust (functional/recursive)

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

Type Signatures

Concept	OCaml	Rust
abstraction mechanism	`module type MONOID` (signature)	`trait Monoid`
empty	`val empty : t`	`fn empty() -> Self`
combine	`val combine : t -> t -> t`	`fn combine(self, other: Self) -> Self`
dispatch	first-class module passed at call site	monomorphized via trait bound at compile time
disambiguation for `int`	`module Sum` and `module Product` (different namespaces)	`struct Sum(i32)` and `struct Product(i32)` (newtype wrappers)

Key Insights

Abstraction mechanism: OCaml uses first-class modules — the monoid implementation is passed explicitly as a value at the call site: reduce (module Sum) list. Rust uses trait bounds resolved at compile time: reduce_monoid::<Sum>(items). The OCaml approach is more dynamic (you can choose the implementation at runtime); Rust's approach is monomorphized (each instantiation compiles to a specialized function, with zero runtime overhead).

Type disambiguation: In OCaml, Sum and Product are distinct modules even though both wrap int — module namespaces prevent any conflict. In Rust, you cannot implement the same trait twice for the same type, so Sum(i32) and Product(i32) are newtype wrappers — thin structs that each get their own impl Monoid.

Clone requirement: OCaml reduce uses List.fold_left with M.empty and M.combine, sharing the accumulator via GC. Rust's reduce_monoid needs T: Clone to call .cloned() on the slice iterator, producing owned values for fold. The accumulator is moved into each combine call rather than shared.

Consuming combine: Rust's combine(self, other: Self) -> Self takes ownership of both operands, modeling the "consume inputs, produce result" functional style. This avoids the need for copying inside combine — the values are simply consumed.

Monoid laws: Neither OCaml nor Rust can enforce the three monoid laws (closure, associativity, identity) in the type system — they are a semantic contract that impl authors must uphold. OCaml module sealing doesn't help here either; both languages rely on documentation and tests.

When to Use Each Style

Use idiomatic Rust (iterator fold) when: Combining a slice of Monoid values — iter().cloned().fold(T::empty(), T::combine) is a zero-overhead, inlined loop in release builds. Use recursive Rust when: Teaching the OCaml parallel, or when the collection is a custom recursive structure (tree, list) rather than a flat slice.

Exercises

Implement a Max monoid over i32 using i32::MIN as the identity element and i32::max as combine, wrapped in a newtype, and verify that reduce_monoid on an empty slice returns i32::MIN

Implement a StringConcat monoid wrapping String with "" as identity and + as combine, then verify that reducing an empty slice returns an empty string and reducing ["hello", " ", "world"] returns "hello world"

Write a mconcat<T: Monoid + Clone>(xss: &[Vec<T>]) -> T function that reduces each inner Vec independently and then combines those results — verifying that the order of combination does not affect the output (associativity)

Open Source Repos

functional-rust

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

Rust