1103 Intermediate

Monoid Pattern — Trait-Based Combining

Functional Programming

Tutorial

The Problem

Define a Monoid trait with an identity element and an associative combine operation, then implement concat_all to fold any list of monoids into a single value using the trait.

🎯 Learning Outcomes

• How OCaml's first-class module system (module type MONOID) translates to Rust traits

• Implement concat_all as a generic fold using trait bounds: works for any type that is a Monoid

• See how i32 (addition monoid) and String (concatenation monoid) share the same interface

Code Example

#![allow(clippy::all)]
/// Monoid trait — a type with an identity element and an associative combine.
pub trait Monoid {
    fn empty() -> Self;
    fn combine(self, other: Self) -> Self;
}

/// Fold a list using a Monoid, starting from the identity element.
pub fn concat_all<M: Monoid>(items: impl IntoIterator<Item = M>) -> M {
    items.into_iter().fold(M::empty(), M::combine)
}

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

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

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

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

    #[test]
    fn test_empty_sum() {
        assert_eq!(concat_all(std::iter::empty::<i32>()), 0);
    }

    #[test]
    fn test_concat_strings() {
        let words = ["hello".to_string(), " ".to_string(), "world".to_string()];
        assert_eq!(concat_all(words), "hello world");
    }

    #[test]
    fn test_single_element() {
        assert_eq!(concat_all([42i32]), 42);
    }
}

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

Polymorphism mechanism: OCaml uses first-class modules passed as values; Rust uses generic type parameters with trait bounds resolved at compile time

Identity access: OCaml calls M.empty via the module; Rust calls M::empty() as an associated function — both are monomorphized per type

Call site: OCaml explicitly passes the module (module Sum); Rust infers the monoid implementation from the type of the collection elements

OCaml Approach

OCaml uses module type MONOID = sig type t; val empty : t; val combine : t -> t -> t end and a higher-kinded concat_all (type a) (module M : MONOID with type t = a). First-class modules are passed at the call site: concat_all (module Sum) [1;2;3;4;5].

Full Source

#![allow(clippy::all)]
/// Monoid trait — a type with an identity element and an associative combine.
pub trait Monoid {
    fn empty() -> Self;
    fn combine(self, other: Self) -> Self;
}

/// Fold a list using a Monoid, starting from the identity element.
pub fn concat_all<M: Monoid>(items: impl IntoIterator<Item = M>) -> M {
    items.into_iter().fold(M::empty(), M::combine)
}

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

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

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

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

    #[test]
    fn test_empty_sum() {
        assert_eq!(concat_all(std::iter::empty::<i32>()), 0);
    }

    #[test]
    fn test_concat_strings() {
        let words = ["hello".to_string(), " ".to_string(), "world".to_string()];
        assert_eq!(concat_all(words), "hello world");
    }

    #[test]
    fn test_single_element() {
        assert_eq!(concat_all([42i32]), 42);
    }
}

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

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

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

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

    #[test]
    fn test_empty_sum() {
        assert_eq!(concat_all(std::iter::empty::<i32>()), 0);
    }

    #[test]
    fn test_concat_strings() {
        let words = ["hello".to_string(), " ".to_string(), "world".to_string()];
        assert_eq!(concat_all(words), "hello world");
    }

    #[test]
    fn test_single_element() {
        assert_eq!(concat_all([42i32]), 42);
    }
}

Exercises

Implement Monoid for Vec<T> where empty() is vec![] and combine is concatenation — verify with concat_all

Implement a Product newtype over i32 (identity = 1, combine = multiplication) and fold [1, 2, 3, 4, 5] into their product

Implement mconcat as an alias for concat_all and verify that mconcat([empty]) == empty for all implementations

Open Source Repos

functional-rust

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

Rust