1084 Intermediate

Monoid Pattern

Functional Programming

Tutorial

The Problem

Demonstrates the monoid algebraic structure — a type with an identity element and an associative binary operation — and how to implement it generically to reduce collections uniformly.

🎯 Learning Outcomes

• Understand what makes a monoid (identity + associativity) and why it matters for generic reduction

• Implement a trait-based abstraction that works across multiple concrete types

• Use fold with a monoid identity to collapse collections without special-casing empty inputs

Code Example

#![allow(clippy::all)]
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!"

Key Differences

Abstraction mechanism: OCaml uses parameterized modules (first-class modules) vs Rust uses traits with generic type parameters

Type disambiguation: OCaml scopes implementations by module namespace vs Rust requires newtype wrappers to implement the same trait for the same underlying type

Identity element: OCaml expresses empty as a module-level value vs Rust requires an associated function empty() -> Self

OCaml Approach

OCaml expresses monoids as first-class modules satisfying a MONOID signature, passing them explicitly at the call site via locally abstract types. This avoids newtypes entirely — the integer type is reused directly under different module implementations.

Full Source

#![allow(clippy::all)]
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));
    }
}

Exercises

Implement a Max monoid over integers using i32::MIN as the identity and extend reduce_monoid to find the maximum of a slice

Implement a StringConcat monoid and verify that reduce_monoid on an empty slice returns an empty string

Add a combine_all function that takes two slices of the same monoid type and interleaves their reductions, then verify associativity holds

Open Source Repos

functional-rust

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

Rust