• Traits define shared behaviour — like interfaces but with default implementations
• Generics with trait bounds: fn process
• Static dispatch (impl Trait) = zero cost; dynamic dispatch (dyn Trait) = runtime flexibility via vtable
• Blanket implementations apply traits to all types matching a bound
• Associated types and supertraits enable complex type relationships
pub trait Semigroup {
fn append(self, other: Self) -> Self;
}
// Can't write two different impls for i64 directly —
// instead, use newtypes to select the instance:
pub struct Sum(pub i64); // "addition" semantics
pub struct Product(pub i64); // "multiplication" semantics
impl Semigroup for Sum {
fn append(self, other: Self) -> Self { Sum(self.0 + other.0) }
}
impl Semigroup for Product {
fn append(self, other: Self) -> Self { Product(self.0 * other.0) }
}pub trait Monoid: Semigroup {
fn empty() -> Self;
}
pub fn fold<M: Monoid>(iter: impl IntoIterator<Item = M>) -> M {
iter.into_iter().fold(M::empty(), |acc, x| acc.append(x))
}
pub fn fold_map<A, M: Monoid>(iter: impl IntoIterator<Item = A>, f: impl Fn(A) -> M) -> M {
iter.into_iter().map(f).fold(M::empty(), |acc, x| acc.append(x))
}
// Choose the instance by selecting the newtype:
let nums = vec![1i64, 2, 3, 4, 5];
let sum = fold_map(nums.iter().copied(), Sum); // Sum(15)
let product = fold_map(nums.iter().copied(), Product); // Product(120)
let max = fold_map(nums.iter().copied(), Max); // Max(5)// Imagine Vec<T> is from another crate and Semigroup is also external.
// We can't impl Semigroup for Vec<T>, but we CAN for our own newtype:
pub struct Concat<T>(pub Vec<T>);
impl<T: Clone> Semigroup for Concat<T> {
fn append(mut self, other: Self) -> Self {
self.0.extend_from_slice(&other.0);
self
}
}| Concept | OCaml | Rust |
|---|---|---|
| Instance uniqueness | Enforced by modules — instances are explicit values | Orphan rule — compiler error on duplicate impls |
| Multiple instances for one type | Different modules, explicitly applied | Newtype wrappers — different types, different impls |
| Selecting an instance | Pass the module explicitly | Wrap the value in the appropriate newtype |
| Foreign-type restriction | None — functors are explicit | Orphan rule applies — newtype required |
| Coherence mechanism | No global coherence — users manage | Global coherence guaranteed by compiler |
// Coherence rules (orphan rules): you can only implement a trait for a type if
// either the trait or the type is defined in your crate.
//
// This prevents conflicting implementations across crates (unlike Haskell,
// where orphan instances cause coherence problems).
//
// The idiomatic Rust solution: the NEWTYPE PATTERN.
// Wrap a foreign type in a local struct — now it's "your" type.
//
// OCaml sidesteps this entirely because typeclass instances are explicit
// module values, not implicit. Rust's solution is the newtype wrapper.
use std::fmt;
// ── Semigroup trait ───────────────────────────────────────────────────────────
pub trait Semigroup {
fn append(self, other: Self) -> Self;
}
pub trait Monoid: Semigroup {
fn empty() -> Self;
}
// ── Direct impls for types we "own" ──────────────────────────────────────────
impl Semigroup for String {
fn append(mut self, other: Self) -> Self {
self.push_str(&other);
self
}
}
impl Monoid for String {
fn empty() -> Self { String::new() }
}
impl Semigroup for Vec<u8> {
fn append(mut self, mut other: Self) -> Self {
self.extend(other.drain(..));
self
}
}
impl Monoid for Vec<u8> {
fn empty() -> Self { Vec::new() }
}
// ── The orphan rule in action ─────────────────────────────────────────────────
// We cannot write: `impl Semigroup for i32 { ... }` in a different crate
// if both `Semigroup` and `i32` come from other crates.
// Here, `Semigroup` is ours, so we CAN impl it for i32 directly.
// But for demonstration, we show the NEWTYPE pattern for multiple instances.
// ── Newtype wrappers — multiple Semigroup instances for i32 ──────────────────
/// Sum semigroup: append = +
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Sum(pub i64);
impl Semigroup for Sum {
fn append(self, other: Self) -> Self { Sum(self.0 + other.0) }
}
impl Monoid for Sum {
fn empty() -> Self { Sum(0) }
}
impl fmt::Display for Sum {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.0) }
}
/// Product semigroup: append = *
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Product(pub i64);
impl Semigroup for Product {
fn append(self, other: Self) -> Self { Product(self.0 * other.0) }
}
impl Monoid for Product {
fn empty() -> Self { Product(1) }
}
impl fmt::Display for Product {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{}", self.0) }
}
/// Max monoid: append = max, identity = i64::MIN
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Max(pub i64);
impl Semigroup for Max {
fn append(self, other: Self) -> Self { Max(self.0.max(other.0)) }
}
impl Monoid for Max {
fn empty() -> Self { Max(i64::MIN) }
}
/// Min monoid: append = min, identity = i64::MAX
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Min(pub i64);
impl Semigroup for Min {
fn append(self, other: Self) -> Self { Min(self.0.min(other.0)) }
}
impl Monoid for Min {
fn empty() -> Self { Min(i64::MAX) }
}
/// All (boolean and): semigroup over bool
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct All(pub bool);
impl Semigroup for All {
fn append(self, other: Self) -> Self { All(self.0 && other.0) }
}
impl Monoid for All {
fn empty() -> Self { All(true) }
}
/// Any (boolean or): semigroup over bool
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Any(pub bool);
impl Semigroup for Any {
fn append(self, other: Self) -> Self { Any(self.0 || other.0) }
}
impl Monoid for Any {
fn empty() -> Self { Any(false) }
}
// ── Generic fold using Monoid ─────────────────────────────────────────────────
pub fn fold<M: Monoid, I: IntoIterator<Item = M>>(iter: I) -> M {
iter.into_iter().fold(M::empty(), |acc, x| acc.append(x))
}
pub fn fold_map<A, M: Monoid, F: Fn(A) -> M, I: IntoIterator<Item = A>>(
iter: I,
f: F,
) -> M {
iter.into_iter().map(f).fold(M::empty(), |acc, x| acc.append(x))
}
// ── Newtype to wrap a standard library type we don't own ─────────────────────
// Imagine `Vec<T>` is from a foreign crate — we wrap it to add our trait.
#[derive(Debug, Clone)]
pub struct Concat<T>(pub Vec<T>);
impl<T: Clone> Semigroup for Concat<T> {
fn append(mut self, other: Self) -> Self {
self.0.extend_from_slice(&other.0);
self
}
}
impl<T: Clone> Monoid for Concat<T> {
fn empty() -> Self { Concat(Vec::new()) }
}
fn main() {
let nums: Vec<i64> = vec![1, 2, 3, 4, 5];
// Choose the instance explicitly by wrapping
let sum = fold_map(nums.iter().copied(), Sum);
let product = fold_map(nums.iter().copied(), Product);
let max = fold_map(nums.iter().copied(), Max);
let min = fold_map(nums.iter().copied(), Min);
println!("sum = {}", sum);
println!("product = {}", product);
println!("max = {:?}", max);
println!("min = {:?}", min);
// Strings
let words = ["a", "b", "c"];
let joined: String = fold_map(words.iter().copied(), String::from);
println!("concat = {}", joined);
// Boolean monoids
let bools = [true, true, false, true];
let all: All = fold_map(bools.iter().copied(), All);
let any: Any = fold_map(bools.iter().copied(), Any);
println!("all = {:?}", all);
println!("any = {:?}", any);
// Newtype wrapping Vec for Concat
let parts = vec![
Concat(vec![1, 2]),
Concat(vec![3, 4]),
Concat(vec![5]),
];
let merged: Concat<i32> = fold(parts);
println!("concat vec = {:?}", merged.0);
// Demonstrate no orphan rule violation:
// - Sum/Product/etc are OUR types → we can impl OUR Semigroup for them.
// - If std's Add were the trait and i32 were both external,
// we'd need a newtype. With OUR trait we're fine.
println!("\nCoherence: no orphan violations — newtype pattern works.");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sum_monoid() {
let v = vec![1, 2, 3, 4, 5];
let s = fold_map(v, Sum);
assert_eq!(s, Sum(15));
}
#[test]
fn test_product_monoid() {
let v = vec![1, 2, 3, 4, 5];
let p = fold_map(v, Product);
assert_eq!(p, Product(120));
}
#[test]
fn test_string_semigroup() {
let s = "hello".to_string().append(" world".to_string());
assert_eq!(s, "hello world");
}
#[test]
fn test_fold_string() {
let result: String = fold_map(["a", "b", "c"].iter().copied(), String::from);
assert_eq!(result, "abc");
}
#[test]
fn test_all_any() {
let all_true = fold_map([true, true, true].iter().copied(), All);
let any_false = fold_map([false, false, true].iter().copied(), Any);
assert_eq!(all_true, All(true));
assert_eq!(any_false, Any(true));
}
#[test]
fn test_concat_newtype() {
let parts = vec![Concat(vec![1, 2]), Concat(vec![3, 4])];
let merged = fold(parts);
assert_eq!(merged.0, vec![1, 2, 3, 4]);
}
#[test]
fn test_max_min() {
let nums = [3, 1, 4, 1, 5, 9, 2, 6];
let max = fold_map(nums.iter().copied(), Max);
let min = fold_map(nums.iter().copied(), Min);
assert_eq!(max, Max(9));
assert_eq!(min, Min(1));
}
}
(* OCaml avoids the Haskell coherence/orphan problem because type class
instances are just module values, not implicit.
You explicitly choose which instance to use. *)
(* Semigroup: two implementations of "append" for the same type *)
module type SEMIGROUP = sig
type t
val append : t -> t -> t
end
(* Two different semigroup instances for integers *)
module IntSum : SEMIGROUP with type t = int = struct
type t = int
let append = ( + )
end
module IntProduct : SEMIGROUP with type t = int = struct
type t = int
let append = ( * )
end
(* Explicitly pass the instance — no ambiguity *)
module Fold (S : SEMIGROUP) = struct
let fold_map f lst =
match List.map f lst with
| [] -> failwith "empty list"
| x :: xs -> List.fold_left S.append x xs
end
module SumFold = Fold (IntSum)
module ProductFold = Fold (IntProduct)
let () =
let nums = [1; 2; 3; 4; 5] in
Printf.printf "sum = %d\n" (SumFold.fold_map (fun x -> x) nums);
Printf.printf "product = %d\n" (ProductFold.fold_map (fun x -> x) nums);
(* No orphan problem: instances live at module level, chosen explicitly *)
let concat_strings = Fold (struct
type t = string
let append = ( ^ )
end) in
Printf.printf "concat = %s\n" (concat_strings.fold_map (fun x -> x) ["a";"b";"c"])
---
🐪 Show OCaml equivalent
(* Define TWO comparison modules for the same type *)
module PersonByName : COMPARABLE with type t = person = struct
type t = person
let compare a b = String.compare a.name b.name
end
module PersonByAge : COMPARABLE with type t = person = struct
type t = person
let compare a b = Int.compare a.age b.age
end
(* Use a functor — pass the module you want *)
module SortByName = SortWith(PersonByName)
module SortByAge = SortWith(PersonByAge)
(* Or use first-class modules at the call site *)
let sorted = sort_with (module PersonByName) people
Key: Both modules exist simultaneously. You choose at each call site.
---
// Default ordering: by name
impl Ord for Person {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.name.cmp(&other.name)
}
}
// Can't add a second Ord impl for Person! Compiler rejects it.
// Instead, wrap in a newtype:
struct SortByAge(Person);
impl Ord for SortByAge {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.0.age.cmp(&other.0.age)
}
}
// Usage:
people.sort(); // by name (default)
let mut by_age: Vec<SortByAge> = people.into_iter().map(SortByAge).collect();
by_age.sort(); // by age (newtype)Key: Only one `Ord` per type. Newtype creates a distinct type for alternative ordering.
---
| Aspect | OCaml | Rust |
|---|---|---|
| Multiple orderings for same type | ✅ Define separate modules | 🔧 Newtype wrapper per ordering |
| How you select the ordering | Pass module explicitly | Use the appropriate newtype |
| Compiler enforcement | None — you pick at call site | Strict — one impl per (Type, Trait) |
| Risk of accidental wrong impl | Possible (wrong module passed) | Low (type system distinguishes) |
| Verbosity | Moderate (functor/module syntax) | Moderate (newtype boilerplate) |
| Cross-crate safety | N/A (no global resolution) | Orphan rule prevents conflicts |
OCaml says: "Here are multiple implementations. You, the programmer, choose which one to use each time."
Rust says: "There is exactly ONE implementation. If you need another, make a new type."
OCaml's approach is more flexible — you can swap implementations freely. Rust's approach is more predictable — you never wonder which impl is in effect.
Both are valid design choices. The newtype pattern in Rust achieves similar flexibility to OCaml's explicit module passing, at the cost of wrapping/unwrapping.
---
Rust adds another coherence tool with no OCaml equivalent:
mod sealed { pub trait Sealed {} }
pub trait MyProtocol: sealed::Sealed {
fn execute(&self) -> String;
}
// Only this crate can impl Sealed → only this crate controls MyProtocol implsOCaml doesn't need this because module implementations are always explicit — there's no "ambient" implementation to protect against.