1118 Advanced

Monoid Pattern — Generic Combining

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Monoid Pattern — Generic Combining" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Implement a generic `concat_all` function that folds any list using its monoid instance (identity element + associative binary operation), parameterized over Sum, Product, string Concat, and boolean All. Key difference from OCaml: 1. **Module vs Trait:** OCaml passes the implementation as a first

Tutorial

The Problem

Implement a generic concat_all function that folds any list using its monoid instance (identity element + associative binary operation), parameterized over Sum, Product, string Concat, and boolean All.

🎯 Learning Outcomes

• How Rust traits encode type classes (here: Monoid) that OCaml encodes with module signatures

• Using fold as the canonical way to collapse a collection via a monoid

• Newtype wrappers (Sum, Product, …) to provide multiple monoid instances for the same base type

• Trait bounds in generic functions replace OCaml's first-class module passing

🦀 The Rust Way

Rust defines a Monoid trait with empty() and combine(). Newtype structs (Sum(i64), Product(i64), Concat(String), All(bool)) each impl Monoid. concat_all<T: Monoid> uses Iterator::fold with T::empty() as the seed—no runtime dispatch, no allocation, zero overhead.

Code Example

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

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

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) }
}
// … Product, Concat, All follow the same pattern

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
module Concat  = struct type t = string let empty = ""   let combine = (^)  end
module All     = struct type t = bool   let empty = true let combine = (&&) end

Key Differences

Module vs Trait: OCaml passes the implementation as a first-class module argument; Rust resolves it via the generic type parameter at compile time.

Multiple instances per type: OCaml creates distinct modules; Rust uses newtype wrappers to avoid conflicting impls on i64.

Identity element: OCaml stores empty as a module value; Rust uses an associated function fn empty() -> Self.

Recursion vs iterator: OCaml's fold_left is a library function; Rust's Iterator::fold works on any IntoIterator, accepting slices, arrays, or lazy chains.

OCaml Approach

OCaml defines a MONOID module signature and accepts first-class modules at call sites: concat_all (module Sum) [1;2;3;4;5]. Separate modules (Sum, Product, Concat, All) implement the signature, and List.fold_left does the combining.

Full Source

#![allow(dead_code)]
// Monoid typeclass pattern using Rust traits.
// OCaml uses first-class modules to pass MONOID implementations.
// Rust uses traits with associated constants/methods and zero-sized marker types.

// ── Monoid trait ──────────────────────────────────────────────────────────────

/// A type with an identity element and an associative binary operation.
pub trait Monoid {
    fn empty() -> Self;
    fn combine(self, other: Self) -> Self;
}

// ── Idiomatic: use the trait bound directly ───────────────────────────────────

/// Fold a slice using its Monoid instance.
/// OCaml: `List.fold_left M.combine M.empty lst`
pub fn concat_all<T: Monoid>(items: impl IntoIterator<Item = T>) -> T {
    items.into_iter().fold(T::empty(), T::combine)
}

// ── Concrete Monoid instances ─────────────────────────────────────────────────

/// Integer addition monoid.
#[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)
    }
}

/// Integer multiplication monoid.
#[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.
#[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 conjunction (all-true) monoid.
#[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)
    }
}

// ── Functional / recursive style ─────────────────────────────────────────────

/// Same operation written with explicit recursion, mirroring OCaml's `fold_left`.
pub fn concat_all_rec<T: Monoid + Clone>(items: &[T]) -> T {
    match items {
        [] => T::empty(),
        [head, rest @ ..] => head.clone().combine(concat_all_rec(rest)),
    }
}

// ── Tests ─────────────────────────────────────────────────────────────────────

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

    // -- concat_all (idiomatic) ------------------------------------------------

    #[test]
    fn test_sum_empty() {
        let result = concat_all::<Sum>([]);
        assert_eq!(result, Sum(0));
    }

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

    #[test]
    fn test_sum_multiple() {
        let result = concat_all([1, 2, 3, 4, 5].map(Sum));
        assert_eq!(result, Sum(15));
    }

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

    #[test]
    fn test_product_multiple() {
        let result = concat_all([1, 2, 3, 4, 5].map(Product));
        assert_eq!(result, Product(120));
    }

    #[test]
    fn test_concat_strings() {
        let words = ["hello", " ", "world"].map(|s| Concat(s.to_owned()));
        assert_eq!(concat_all(words), Concat("hello world".to_owned()));
    }

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

    #[test]
    fn test_all_all_true() {
        let result = concat_all([All(true), All(true), All(true)]);
        assert_eq!(result, All(true));
    }

    #[test]
    fn test_all_with_false() {
        let result = concat_all([All(true), All(true), All(false)]);
        assert_eq!(result, All(false));
    }

    // -- concat_all_rec (recursive) -------------------------------------------

    #[test]
    fn test_rec_sum_empty() {
        let result = concat_all_rec::<Sum>(&[]);
        assert_eq!(result, Sum(0));
    }

    #[test]
    fn test_rec_sum_multiple() {
        let items: Vec<Sum> = [1, 2, 3, 4, 5].map(Sum).to_vec();
        assert_eq!(concat_all_rec(&items), Sum(15));
    }

    #[test]
    fn test_rec_product_multiple() {
        let items: Vec<Product> = [1, 2, 3, 4, 5].map(Product).to_vec();
        assert_eq!(concat_all_rec(&items), Product(120));
    }

    #[test]
    fn test_rec_all_with_false() {
        let items = [All(true), All(false), All(true)];
        assert_eq!(concat_all_rec(&items), All(false));
    }
}

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
module Concat = struct type t = string let empty = "" let combine = (^) end
module All = struct type t = bool let empty = true 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]);
  Printf.printf "concat: %s\n" (concat_all (module Concat) ["hello";" ";"world"]);
  Printf.printf "all: %b\n" (concat_all (module All) [true; true; false])

✓ Tests Rust test suite

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

    // -- concat_all (idiomatic) ------------------------------------------------

    #[test]
    fn test_sum_empty() {
        let result = concat_all::<Sum>([]);
        assert_eq!(result, Sum(0));
    }

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

    #[test]
    fn test_sum_multiple() {
        let result = concat_all([1, 2, 3, 4, 5].map(Sum));
        assert_eq!(result, Sum(15));
    }

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

    #[test]
    fn test_product_multiple() {
        let result = concat_all([1, 2, 3, 4, 5].map(Product));
        assert_eq!(result, Product(120));
    }

    #[test]
    fn test_concat_strings() {
        let words = ["hello", " ", "world"].map(|s| Concat(s.to_owned()));
        assert_eq!(concat_all(words), Concat("hello world".to_owned()));
    }

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

    #[test]
    fn test_all_all_true() {
        let result = concat_all([All(true), All(true), All(true)]);
        assert_eq!(result, All(true));
    }

    #[test]
    fn test_all_with_false() {
        let result = concat_all([All(true), All(true), All(false)]);
        assert_eq!(result, All(false));
    }

    // -- concat_all_rec (recursive) -------------------------------------------

    #[test]
    fn test_rec_sum_empty() {
        let result = concat_all_rec::<Sum>(&[]);
        assert_eq!(result, Sum(0));
    }

    #[test]
    fn test_rec_sum_multiple() {
        let items: Vec<Sum> = [1, 2, 3, 4, 5].map(Sum).to_vec();
        assert_eq!(concat_all_rec(&items), Sum(15));
    }

    #[test]
    fn test_rec_product_multiple() {
        let items: Vec<Product> = [1, 2, 3, 4, 5].map(Product).to_vec();
        assert_eq!(concat_all_rec(&items), Product(120));
    }

    #[test]
    fn test_rec_all_with_false() {
        let items = [All(true), All(false), All(true)];
        assert_eq!(concat_all_rec(&items), All(false));
    }
}

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
module Concat  = struct type t = string let empty = ""   let combine = (^)  end
module All     = struct type t = bool   let empty = true let combine = (&&) end

Rust (idiomatic)

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

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

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) }
}
// … Product, Concat, All follow the same pattern

Rust (functional/recursive)

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

Type Signatures

Concept	OCaml	Rust
Type class / module signature	`module type MONOID = sig type t ... end`	`trait Monoid { fn empty() -> Self; fn combine(self, Self) -> Self; }`
Generic fold function	`val concat_all : (module MONOID with type t = 'a) -> 'a list -> 'a`	`fn concat_all<T: Monoid>(impl IntoIterator<Item=T>) -> T`
Identity element	`val empty : t` (module field)	`fn empty() -> Self` (associated function)
Binary operation	`val combine : t -> t -> t`	`fn combine(self, other: Self) -> Self`
Sum instance	`module Sum = struct type t = int let empty = 0 … end`	`impl Monoid for Sum { … }` on newtype `struct Sum(i64)`
Dispatch mechanism	First-class module passed at call site	Monomorphization via generic type parameter

Key Insights

First-class modules ↔ trait impls: OCaml's (module Sum) at the call site is the runtime carrier of the implementation; Rust's T in concat_all<T: Monoid> is resolved at compile time by the type system—no extra argument needed.

Multiple instances for the same base type: OCaml can have Sum and Product both with type t = int in separate modules and pass either one. Rust cannot have two impl Monoid for i64, so newtype wrappers (Sum(i64), Product(i64)) provide the same capability without ambiguity.

Identity as value vs associated function: OCaml stores empty as a module-level value. Rust makes it fn empty() -> Self—a constructor-like associated function—which is required because trait methods can't be associated constants for non-Copy types in the general case (though const in traits is stabilizing).

**fold universality:** List.fold_left in OCaml is a specialized list function. Rust's Iterator::fold works on any type implementing IntoIterator—arrays, slices, Vec, lazy chains—making the generic combiner more reusable.

Zero-overhead abstraction: Rust monomorphizes concat_all::<Sum> and concat_all::<Product> into separate specialized functions at compile time, matching the performance of hand-written loops. OCaml's first-class modules carry vtables, so there is a small indirection cost.

When to Use Each Style

**Use idiomatic Rust (concat_all with Iterator::fold) when:** folding any iterable collection, especially when performance matters or when you want to compose with other iterator adapters.

**Use recursive Rust (concat_all_rec) when:** demonstrating the OCaml structural recursion pattern for educational purposes, or when working with a recursive algebraic data structure (e.g., a linked list type) where pattern matching is more natural than iteration.

Exercises

Implement a Product<T> newtype monoid wrapping a numeric type and verify concat_all correctly computes the product of a list of numbers.

Build a Dual<M> monoid that reverses the order of the binary operation (i.e., Dual(x).combine(Dual(y)) = y.combine(x)) and use it to find the minimum of a list using the same concat_all machinery.

Compose two monoids into a product monoid (M1, M2) whose operation applies each component monoid independently, then use it to compute the count and sum of a list simultaneously in one pass.

Open Source Repos

functional-rust

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

Rust