1136 Intermediate

Monoid — Fold with Closures and Traits

Pattern MatchingHigher-Order FunctionsType-Class Patterns

Tutorial

The Problem

Implement a generic concat_all function that folds any list using a monoid (an associative binary operation with an identity element), demonstrated with Sum, Product, string Concat, and boolean All.

🎯 Learning Outcomes

• How OCaml's first-class modules translate to Rust closures vs. traits

• Why Rust requires newtypes when the same base type supports multiple monoids

• How std::iter::Sum and std::iter::Product encode numeric monoids in the stdlib

• The difference between static dispatch (generics) and dynamic dispatch (trait objects)

🦀 The Rust Way

Rust offers three equivalent perspectives:

Closures — pass empty and combine explicitly, mirroring OCaml modules

as plain function arguments. Maximally flexible, no trait required.

Traits — encode the monoid contract as a trait Monoid. The compiler

resolves the implementation at compile time (monomorphisation); zero runtime cost. Newtypes (Sum(i32), Product(i32)) replace OCaml's named modules.

**std::iter::Sum / std::iter::Product** — the standard library already

provides these for all numeric types; use them for the common numeric cases.

Code Example

// OCaml's (module M : MONOID with type t = a) becomes two plain arguments:
// the identity value and the combining function.
pub fn concat_with<T>(
    empty: T,
    combine: impl Fn(T, T) -> T,
    items: impl IntoIterator<Item = T>,
) -> T {
    items.into_iter().fold(empty, combine)
}

// Call sites mirror OCaml's `concat_all (module Sum) [...]`:
let sum     = concat_with(0,    |a, b| a + b,   [1, 2, 3, 4, 5]);  // 15
let product = concat_with(1,    |a, b| a * b,   [1, 2, 3, 4, 5]);  // 120
let text    = concat_with("".to_owned(), |a, b| a + &b, [...]); // "hello world"
let all     = concat_with(true, |a, b| a && b,  [true, true, false]); // 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])

Key Differences

First-class modules vs. closures/traits: OCaml passes a module value at

the call site; Rust either passes closures directly or encodes the same information in the type system via traits.

Multiple instances per base type: OCaml uses module names; Rust uses

newtypes to satisfy the coherence/orphan rules.

Identity element: OCaml stores empty as a module value; Rust expresses

it as an associated function fn empty() -> Self on the trait, or as the initial accumulator in fold.

Zero-cost generics: Rust's <M: Monoid> generates one specialised copy per

concrete type; OCaml's first-class modules use runtime dispatch.

OCaml Approach

OCaml uses a first-class module — (module M : MONOID with type t = a) — as a runtime value carrying both the identity (M.empty) and the combiner (M.combine). The locally-abstract type (type a) lets concat_all work over any element type without losing the connection to the module. Multiple modules can share type t = int (Sum and Product) because they are distinguished by name.

Full Source

#![allow(clippy::all)]
// ---------------------------------------------------------------------------
// Solution 1: Closure-based — direct mapping of OCaml first-class modules
//
// OCaml passes `(module M : MONOID with type t = a)` at the call site,
// which bundles an `empty` value and a `combine` function.
// This solution makes that structure explicit: the caller provides both pieces.
// ---------------------------------------------------------------------------

/// Fold a list using an explicit identity element and a combining function.
///
/// This mirrors the OCaml call site precisely:
///   `concat_all (module Sum) [1;2;3;4;5]`
/// becomes:
///   `concat_with(0, |a, b| a + b, [1,2,3,4,5])`
pub fn concat_with<T>(
    empty: T,
    combine: impl Fn(T, T) -> T,
    items: impl IntoIterator<Item = T>,
) -> T {
    items.into_iter().fold(empty, combine)
}

// ---------------------------------------------------------------------------
// Solution 2: Idiomatic Rust — trait with a blanket fold function
//
// The trait encodes the monoid laws as an interface constraint, and the
// compiler resolves the implementation statically (monomorphisation).
// This is zero-cost; no runtime dispatch.
// ---------------------------------------------------------------------------

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

/// Fold a collection of monoidal values into one.
///
/// Equivalent to OCaml's `List.fold_left M.combine M.empty lst`.
pub fn concat_all<M: Monoid>(items: impl IntoIterator<Item = M>) -> M {
    items.into_iter().fold(M::empty(), M::combine)
}

// ---------------------------------------------------------------------------
// Solution 3: Standard-library monoids — Sum and Product built into Rust
//
// For numeric types, the standard library already provides monoid-like
// behaviour through `std::iter::Sum` and `std::iter::Product`, which are
// exactly the sum and product monoids over numeric types.
// ---------------------------------------------------------------------------

/// Sum a sequence of numbers using the stdlib monoid (zero identity, + combine).
pub fn sum_all<T: std::iter::Sum>(items: impl IntoIterator<Item = T>) -> T {
    items.into_iter().sum()
}

/// Multiply a sequence of numbers using the stdlib monoid (one identity, * combine).
pub fn product_all<T: std::iter::Product>(items: impl IntoIterator<Item = T>) -> T {
    items.into_iter().product()
}

// ---------------------------------------------------------------------------
// Newtype wrappers for the Monoid trait — one per OCaml "module instance"
//
// OCaml can have two modules with `type t = int` (Sum and Product) because
// modules are distinguished by name. Rust uses newtypes for the same purpose:
// coherence rules prevent two `impl Monoid for i32` in the same crate.
// ---------------------------------------------------------------------------

/// Additive monoid over i32  (OCaml: module Sum)
#[derive(Debug, Clone, Copy, 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)
    }
}

/// Multiplicative monoid over i32  (OCaml: module Product)
#[derive(Debug, Clone, Copy, 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)
    }
}

/// String-concatenation monoid  (OCaml: module Concat)
#[derive(Debug, Clone, PartialEq)]
pub struct Concat(pub String);

impl Monoid for Concat {
    fn empty() -> Self {
        Concat(String::new())
    }
    fn combine(self, other: Self) -> Self {
        // Moves `self.0` into a new String and appends `other.0`,
        // reusing the heap buffer of the left-hand side.
        Concat(self.0 + &other.0)
    }
}

/// Boolean-AND monoid  (OCaml: module All)
#[derive(Debug, Clone, Copy, PartialEq)]
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)
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    // --- Solution 1: closure-based ---

    #[test]
    fn test_closure_sum() {
        let result = concat_with(0, |a, b| a + b, [1, 2, 3, 4, 5]);
        assert_eq!(result, 15);
    }

    #[test]
    fn test_closure_product() {
        let result = concat_with(1, |a, b| a * b, [1, 2, 3, 4, 5]);
        assert_eq!(result, 120);
    }

    #[test]
    fn test_closure_concat() {
        let result = concat_with(
            String::new(),
            |a, b| a + &b,
            ["hello".to_owned(), " ".to_owned(), "world".to_owned()],
        );
        assert_eq!(result, "hello world");
    }

    #[test]
    fn test_closure_all_with_false() {
        let result = concat_with(true, |a, b| a && b, [true, true, false]);
        assert_eq!(result, false);
    }

    #[test]
    fn test_closure_empty_list_returns_identity() {
        // The empty-list case returns the identity element unchanged.
        let sum = concat_with(0, |a, b| a + b, std::iter::empty::<i32>());
        assert_eq!(sum, 0);
        let product = concat_with(1, |a, b| a * b, std::iter::empty::<i32>());
        assert_eq!(product, 1);
    }

    // --- Solution 2: trait-based ---

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

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

    #[test]
    fn test_trait_concat_strings() {
        let result = concat_all([
            Concat("hello".into()),
            Concat(" ".into()),
            Concat("world".into()),
        ]);
        assert_eq!(result, Concat("hello world".into()));
    }

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

    #[test]
    fn test_trait_empty_list_identity() {
        assert_eq!(concat_all::<Sum>([]), Sum(0));
        assert_eq!(concat_all::<Product>([]), Product(1));
        assert_eq!(concat_all::<All>([]), All(true));
    }

    // --- Solution 3: std::iter::Sum / Product ---

    #[test]
    fn test_stdlib_sum_matches_closure() {
        let closure_result = concat_with(0, |a, b| a + b, [1, 2, 3, 4, 5]);
        let stdlib_result = sum_all([1, 2, 3, 4, 5]);
        assert_eq!(closure_result, stdlib_result);
    }

    #[test]
    fn test_stdlib_product_matches_closure() {
        let closure_result = concat_with(1, |a, b| a * b, [1, 2, 3, 4, 5]);
        let stdlib_result = product_all([1, 2, 3, 4, 5]);
        assert_eq!(closure_result, stdlib_result);
    }

    // --- Monoid laws ---

    #[test]
    fn test_left_identity_law() {
        // combine(empty, x) == x for all monoids
        let x = Sum(42);
        assert_eq!(Sum::empty().combine(x), x);
    }

    #[test]
    fn test_right_identity_law() {
        // combine(x, empty) == x for all monoids
        let x = Product(7);
        assert_eq!(x.combine(Product::empty()), x);
    }

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

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::*;

    // --- Solution 1: closure-based ---

    #[test]
    fn test_closure_sum() {
        let result = concat_with(0, |a, b| a + b, [1, 2, 3, 4, 5]);
        assert_eq!(result, 15);
    }

    #[test]
    fn test_closure_product() {
        let result = concat_with(1, |a, b| a * b, [1, 2, 3, 4, 5]);
        assert_eq!(result, 120);
    }

    #[test]
    fn test_closure_concat() {
        let result = concat_with(
            String::new(),
            |a, b| a + &b,
            ["hello".to_owned(), " ".to_owned(), "world".to_owned()],
        );
        assert_eq!(result, "hello world");
    }

    #[test]
    fn test_closure_all_with_false() {
        let result = concat_with(true, |a, b| a && b, [true, true, false]);
        assert_eq!(result, false);
    }

    #[test]
    fn test_closure_empty_list_returns_identity() {
        // The empty-list case returns the identity element unchanged.
        let sum = concat_with(0, |a, b| a + b, std::iter::empty::<i32>());
        assert_eq!(sum, 0);
        let product = concat_with(1, |a, b| a * b, std::iter::empty::<i32>());
        assert_eq!(product, 1);
    }

    // --- Solution 2: trait-based ---

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

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

    #[test]
    fn test_trait_concat_strings() {
        let result = concat_all([
            Concat("hello".into()),
            Concat(" ".into()),
            Concat("world".into()),
        ]);
        assert_eq!(result, Concat("hello world".into()));
    }

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

    #[test]
    fn test_trait_empty_list_identity() {
        assert_eq!(concat_all::<Sum>([]), Sum(0));
        assert_eq!(concat_all::<Product>([]), Product(1));
        assert_eq!(concat_all::<All>([]), All(true));
    }

    // --- Solution 3: std::iter::Sum / Product ---

    #[test]
    fn test_stdlib_sum_matches_closure() {
        let closure_result = concat_with(0, |a, b| a + b, [1, 2, 3, 4, 5]);
        let stdlib_result = sum_all([1, 2, 3, 4, 5]);
        assert_eq!(closure_result, stdlib_result);
    }

    #[test]
    fn test_stdlib_product_matches_closure() {
        let closure_result = concat_with(1, |a, b| a * b, [1, 2, 3, 4, 5]);
        let stdlib_result = product_all([1, 2, 3, 4, 5]);
        assert_eq!(closure_result, stdlib_result);
    }

    // --- Monoid laws ---

    #[test]
    fn test_left_identity_law() {
        // combine(empty, x) == x for all monoids
        let x = Sum(42);
        assert_eq!(Sum::empty().combine(x), x);
    }

    #[test]
    fn test_right_identity_law() {
        // combine(x, empty) == x for all monoids
        let x = Product(7);
        assert_eq!(x.combine(Product::empty()), x);
    }

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

Deep Comparison

OCaml vs Rust: Monoid — Fold with Closures and Traits

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

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])

Rust — Solution 1: Closure-based (direct OCaml analogy)

// OCaml's (module M : MONOID with type t = a) becomes two plain arguments:
// the identity value and the combining function.
pub fn concat_with<T>(
    empty: T,
    combine: impl Fn(T, T) -> T,
    items: impl IntoIterator<Item = T>,
) -> T {
    items.into_iter().fold(empty, combine)
}

// Call sites mirror OCaml's `concat_all (module Sum) [...]`:
let sum     = concat_with(0,    |a, b| a + b,   [1, 2, 3, 4, 5]);  // 15
let product = concat_with(1,    |a, b| a * b,   [1, 2, 3, 4, 5]);  // 120
let text    = concat_with("".to_owned(), |a, b| a + &b, [...]); // "hello world"
let all     = concat_with(true, |a, b| a && b,  [true, true, false]); // false

Rust — Solution 2: Trait-based (idiomatic Rust)

pub trait Monoid: Sized {
    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)
}

// Newtypes replace OCaml module names — Sum and Product can both wrap i32
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) }
}

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) }
}

Rust — Solution 3: std::iter::Sum / Product

// The stdlib already knows about numeric monoids:
let sum:     i32 = [1, 2, 3, 4, 5].iter().sum();      // Sum monoid built-in
let product: i32 = [1, 2, 3, 4, 5].iter().product();  // Product monoid built-in

Type Signatures

Concept	OCaml	Rust (closure)	Rust (trait)
Interface	`module type MONOID`	closure pair `(T, Fn(T,T)->T)`	`trait Monoid`
Generic fold	`concat_all (module M) lst`	`concat_with(empty, combine, items)`	`concat_all<M: Monoid>(items)`
Sum identity	`val empty = 0`	literal `0`	`fn empty() -> Self { Sum(0) }`
Sum combine	`val combine = (+)`	`\\|a, b\\| a + b`	`fn combine(self, other: Self) -> Self { Sum(self.0 + other.0) }`
Multiple instances of same base type	two modules with `type t = int`	two calls with different `empty`/`combine`	two newtypes `Sum(i32)`, `Product(i32)`

Key Insights

First-class modules ≈ closure pairs: OCaml's (module M : MONOID with type t = a) packages an identity value and a combining function under a name. Rust closures achieve the same effect by passing these two pieces explicitly — the concat_with signature is a direct structural translation of the OCaml module type.

Traits encode static dispatch: The trait approach moves the empty and combine implementations from the call site into the type itself. Rust's compiler monomorphises concat_all<Sum> and concat_all<Product> into two specialised functions at compile time — equivalent to C++ templates — with zero runtime overhead. OCaml's first-class modules use runtime dispatch via a vtable.

Newtypes solve the coherence problem: OCaml can have module Sum and module Product both with type t = int because modules are distinguished by name. Rust's orphan and coherence rules prohibit two impl Monoid for i32 in the same crate, so newtypes Sum(i32) and Product(i32) each carry their own impl without conflict.

**empty as function vs. stored value:** In OCaml M.empty is a stored module field evaluated once at module definition time. In Rust M::empty() is a function producing the identity on each call. For purely functional (no side-effects) identities the effect is identical; the function form is necessary because Rust trait associated items cannot be arbitrary values of unconstrained type.

Stdlib monoids: For the numeric cases, std::iter::Sum and std::iter::Product are pre-built monoids; calling .sum() or .product() on any iterator of a numeric type is idiomatic Rust and has no boilerplate.

When to Use Each Style

Use the closure-based style when: you need a one-off fold with an unusual identity/combine that doesn't justify a new type, or when teaching the correspondence with OCaml's first-class modules.

Use the trait-based style when: the same monoid instance is reused in many places, or when you want the type system to enforce monoid laws at boundaries (e.g., in generic data structures like segment trees or parallel fold).

**Use std::iter::sum() / .product() when:** you just need numeric aggregation and both the identity and combine are the standard arithmetic ones — this is the most idiomatic Rust for that case.

Exercises

Add a Concat string monoid alongside Sum and Product and verify that concat_all with identity "" correctly joins a list of strings.

Implement a generic mconcat function as a blanket impl on IntoIterator<Item: Monoid> so any iterable of monoidal values can be summed with a single call.

Implement the writer monad using your Monoid abstraction: a Writer<A, W: Monoid> type that pairs a value with a log, where bind concatenates logs using the monoid operation.

Open Source Repos

functional-rust

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

Rust