260 Advanced

Functor Comparable Set

Functors and Modules

Tutorial Video

Text description (accessibility)

This video demonstrates the "Functor Comparable Set" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functors and Modules. Build a generic, deduplicated, ordered set from any type that supports comparison, mirroring OCaml's `Set.Make` functor pattern that produces a new module from a `COMPARABLE` module argument. Key difference from OCaml: 1. **Abstraction mechanism:** OCaml uses *functor application* (`MakeSet(Int)`) to produce a new module at the module level; Rust uses *monomorphisation* of a generic struct at compile time.

Tutorial

The Problem

Build a generic, deduplicated, ordered set from any type that supports comparison, mirroring OCaml's Set.Make functor pattern that produces a new module from a COMPARABLE module argument.

🎯 Learning Outcomes

• How OCaml functors (module-level functions parameterised by modules) map to Rust generic structs with trait bounds

• Using Ord as the Rust analogue of OCaml's COMPARABLE module type

• Maintaining a sorted, deduplicated Vec with binary_search for O(log n) lookup

• Builder-style method chaining (insert returns Self) to replicate OCaml's pipe-operator idiom

🦀 The Rust Way

Rust replaces the functor with a generic struct ComparableSet<T: Ord>. The Ord trait bound plays the role of the COMPARABLE module type — any type implementing Ord (including all primitives and String) can be used. A second struct FunctorSet<T: Ord> replicates OCaml's original list-based strategy (O(n) insert, sort on to_list) to show the direct translation.

Code Example

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ComparableSet<T: Ord> {
    items: Vec<T>,
}

impl<T: Ord> ComparableSet<T> {
    pub fn new() -> Self { ComparableSet { items: Vec::new() } }

    pub fn contains(&self, x: &T) -> bool {
        self.items.binary_search(x).is_ok()
    }

    #[must_use]
    pub fn insert(mut self, x: T) -> Self {
        match self.items.binary_search(&x) {
            Ok(_)    => self,
            Err(pos) => { self.items.insert(pos, x); self }
        }
    }

    pub fn to_sorted_vec(&self) -> &[T] { &self.items }
}

let s = ComparableSet::new().insert(3).insert(1).insert(3).insert(2);
// s.to_sorted_vec() == [1, 2, 3]

module type COMPARABLE = sig
  type t
  val compare : t -> t -> int
end

module MakeSet (C : COMPARABLE) = struct
  type t = C.t list
  let empty = []
  let mem x = List.exists (fun y -> C.compare x y = 0)
  let add x s = if mem x s then s else x :: s
  let to_list s = List.sort C.compare s
end

module IntSet = MakeSet(Int)

let s = IntSet.(empty |> add 3 |> add 1 |> add 3 |> add 2)
(* IntSet.to_list s = [1; 2; 3] *)

Key Differences

Abstraction mechanism: OCaml uses functor application (MakeSet(Int)) to produce a new module at the module level; Rust uses monomorphisation of a generic struct at compile time.

Trait vs module type: COMPARABLE is an OCaml module type specifying compare; Rust uses the built-in Ord trait which every numeric type and String already implements.

Mutability: OCaml's add returns a new value (functional update); Rust's insert consumes self and returns Self, encoding the same immutable-update pattern without hidden clones.

Performance: The idiomatic Rust ComparableSet uses a sorted Vec with binary_search for O(log n) membership test; the OCaml original uses List.exists — O(n) — and sorts on to_list.

OCaml Approach

OCaml defines a COMPARABLE module signature with a compare function, then uses a functor MakeSet(C : COMPARABLE) to produce a new module that contains an ordered set for type C.t. The resulting IntSet and StringSet modules are completely separate types, each with their own empty, mem, add, and to_list functions.

Full Source

#![allow(clippy::all)]
// A generic ordered set backed by a sorted Vec, parameterised by the element
// type's `Ord` bound — the Rust equivalent of OCaml's `Map.Make` / `Set.Make`
// functor pattern.
//
// OCaml uses a *functor* (a module-level function) to create a new Set module
// for a specific `COMPARABLE` type.  Rust achieves the same result with a
// generic struct and a trait bound: `ComparableSet<T: Ord>`.

// ---------------------------------------------------------------------------
// Solution 1: Idiomatic Rust — generic struct with Ord trait bound
// ---------------------------------------------------------------------------

/// An ordered, deduplicated set of elements that implement `Ord`.
///
/// Mirrors OCaml's `Set.Make(COMPARABLE)` functor output.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ComparableSet<T: Ord> {
    items: Vec<T>,
}

impl<T: Ord> Default for ComparableSet<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Ord> ComparableSet<T> {
    /// Create an empty set — `MakeSet(C).empty`.
    pub fn new() -> Self {
        ComparableSet { items: Vec::new() }
    }

    /// Return `true` if `x` is a member — `mem x s`.
    pub fn contains(&self, x: &T) -> bool {
        self.items.binary_search(x).is_ok()
    }

    /// Insert `x`, preserving sorted order and uniqueness — `add x s`.
    ///
    /// Returns a new set (immutable-style), matching the OCaml API where
    /// `add` returns a new set value rather than mutating in place.
    #[must_use]
    pub fn insert(mut self, x: T) -> Self {
        match self.items.binary_search(&x) {
            Ok(_) => self, // already present — set unchanged
            Err(pos) => {
                self.items.insert(pos, x);
                self
            }
        }
    }

    /// Return a sorted slice of all elements — `to_list s`.
    pub fn to_sorted_vec(&self) -> &[T] {
        &self.items
    }

    /// Number of elements in the set.
    pub fn len(&self) -> usize {
        self.items.len()
    }

    /// Return `true` if the set contains no elements.
    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }
}

// ---------------------------------------------------------------------------
// Solution 2: Functional / recursive style — closer to OCaml list-based impl
// ---------------------------------------------------------------------------
//
// OCaml's `MakeSet` stores elements in an unsorted list and sorts on `to_list`.
// We replicate that approach with a wrapper that defers sorting.

/// An unordered, deduplicated set of elements backed by a `Vec`.
///
/// Matches the OCaml implementation strategy: insertion is O(n), `to_list`
/// sorts on demand.  Contrast with `ComparableSet` which keeps items sorted.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FunctorSet<T: Ord> {
    items: Vec<T>,
}

impl<T: Ord> Default for FunctorSet<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Ord> FunctorSet<T> {
    pub fn new() -> Self {
        FunctorSet { items: Vec::new() }
    }

    /// OCaml: `let mem x = List.exists (fun y -> C.compare x y = 0)`
    pub fn mem(&self, x: &T) -> bool {
        self.items.iter().any(|y| y == x)
    }

    /// OCaml: `let add x s = if mem x s then s else x :: s`
    ///
    /// Renamed to `push` to avoid confusion with `std::ops::Add`.
    #[must_use]
    pub fn push(mut self, x: T) -> Self {
        if self.mem(&x) {
            self
        } else {
            self.items.push(x);
            self
        }
    }

    /// OCaml: `let to_list s = List.sort C.compare s`
    pub fn to_list(&self) -> Vec<&T> {
        let mut sorted: Vec<&T> = self.items.iter().collect();
        sorted.sort();
        sorted
    }
}

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

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

    // --- ComparableSet (idiomatic) ---

    #[test]
    fn test_comparable_set_empty() {
        let s: ComparableSet<i32> = ComparableSet::new();
        assert!(s.is_empty());
        assert_eq!(s.len(), 0);
        assert!(!s.contains(&1));
    }

    #[test]
    fn test_comparable_set_single_insert() {
        let s = ComparableSet::new().insert(42);
        assert_eq!(s.len(), 1);
        assert!(s.contains(&42));
        assert!(!s.contains(&0));
    }

    #[test]
    fn test_comparable_set_deduplication() {
        let s = ComparableSet::new()
            .insert(3)
            .insert(1)
            .insert(3) // duplicate — ignored
            .insert(2);
        assert_eq!(s.len(), 3);
        assert_eq!(s.to_sorted_vec(), &[1, 2, 3]);
    }

    #[test]
    fn test_comparable_set_sorted_order() {
        let s = ComparableSet::new()
            .insert(5)
            .insert(1)
            .insert(4)
            .insert(2)
            .insert(3);
        assert_eq!(s.to_sorted_vec(), &[1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_comparable_set_strings() {
        let s = ComparableSet::new()
            .insert("banana")
            .insert("apple")
            .insert("cherry")
            .insert("apple"); // duplicate
        assert_eq!(s.len(), 3);
        assert_eq!(s.to_sorted_vec(), &["apple", "banana", "cherry"]);
    }

    // --- FunctorSet (OCaml-style functional) ---

    #[test]
    fn test_functor_set_empty() {
        let s: FunctorSet<i32> = FunctorSet::new();
        assert!(!s.mem(&1));
        assert_eq!(s.to_list(), Vec::<&i32>::new());
    }

    #[test]
    fn test_functor_set_push_and_mem() {
        let s = FunctorSet::new().push(10).push(20).push(10); // 10 deduplicated
        assert!(s.mem(&10));
        assert!(s.mem(&20));
        assert!(!s.mem(&30));
        assert_eq!(s.items.len(), 2);
    }

    #[test]
    fn test_functor_set_to_list_sorted() {
        // mirrors the OCaml: IntSet.(empty |> add 3 |> add 1 |> add 3 |> add 2)
        let s = FunctorSet::new().push(3).push(1).push(3).push(2);
        assert_eq!(s.to_list(), vec![&1, &2, &3]);
    }

    #[test]
    fn test_functor_set_string() {
        let s = FunctorSet::new()
            .push("gamma")
            .push("alpha")
            .push("beta")
            .push("alpha");
        assert_eq!(s.to_list(), vec![&"alpha", &"beta", &"gamma"]);
    }
}

(* OCaml functor pattern: COMPARABLE module type + MakeSet functor *)

module type COMPARABLE = sig
  type t
  val compare : t -> t -> int
end

module MakeSet (C : COMPARABLE) = struct
  type t = C.t list
  let empty = []
  let mem x = List.exists (fun y -> C.compare x y = 0)
  let add x s = if mem x s then s else x :: s
  let to_list s = List.sort C.compare s
end

(* Instantiate the functor for Int and String *)
module IntSet = MakeSet(Int)
module StringSet = MakeSet(String)

let () =
  (* Int set — duplicates are ignored *)
  let s = IntSet.(empty |> add 3 |> add 1 |> add 3 |> add 2) in
  assert (IntSet.to_list s = [1; 2; 3]);
  assert (IntSet.mem 1 s = true);
  assert (IntSet.mem 5 s = false);

  (* String set *)
  let ss = StringSet.(empty |> add "banana" |> add "apple" |> add "cherry" |> add "apple") in
  assert (StringSet.to_list ss = ["apple"; "banana"; "cherry"]);

  List.iter (Printf.printf "%d ") (IntSet.to_list s);
  print_newline ();
  print_endline "ok"

✓ Tests Rust test suite

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

    // --- ComparableSet (idiomatic) ---

    #[test]
    fn test_comparable_set_empty() {
        let s: ComparableSet<i32> = ComparableSet::new();
        assert!(s.is_empty());
        assert_eq!(s.len(), 0);
        assert!(!s.contains(&1));
    }

    #[test]
    fn test_comparable_set_single_insert() {
        let s = ComparableSet::new().insert(42);
        assert_eq!(s.len(), 1);
        assert!(s.contains(&42));
        assert!(!s.contains(&0));
    }

    #[test]
    fn test_comparable_set_deduplication() {
        let s = ComparableSet::new()
            .insert(3)
            .insert(1)
            .insert(3) // duplicate — ignored
            .insert(2);
        assert_eq!(s.len(), 3);
        assert_eq!(s.to_sorted_vec(), &[1, 2, 3]);
    }

    #[test]
    fn test_comparable_set_sorted_order() {
        let s = ComparableSet::new()
            .insert(5)
            .insert(1)
            .insert(4)
            .insert(2)
            .insert(3);
        assert_eq!(s.to_sorted_vec(), &[1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_comparable_set_strings() {
        let s = ComparableSet::new()
            .insert("banana")
            .insert("apple")
            .insert("cherry")
            .insert("apple"); // duplicate
        assert_eq!(s.len(), 3);
        assert_eq!(s.to_sorted_vec(), &["apple", "banana", "cherry"]);
    }

    // --- FunctorSet (OCaml-style functional) ---

    #[test]
    fn test_functor_set_empty() {
        let s: FunctorSet<i32> = FunctorSet::new();
        assert!(!s.mem(&1));
        assert_eq!(s.to_list(), Vec::<&i32>::new());
    }

    #[test]
    fn test_functor_set_push_and_mem() {
        let s = FunctorSet::new().push(10).push(20).push(10); // 10 deduplicated
        assert!(s.mem(&10));
        assert!(s.mem(&20));
        assert!(!s.mem(&30));
        assert_eq!(s.items.len(), 2);
    }

    #[test]
    fn test_functor_set_to_list_sorted() {
        // mirrors the OCaml: IntSet.(empty |> add 3 |> add 1 |> add 3 |> add 2)
        let s = FunctorSet::new().push(3).push(1).push(3).push(2);
        assert_eq!(s.to_list(), vec![&1, &2, &3]);
    }

    #[test]
    fn test_functor_set_string() {
        let s = FunctorSet::new()
            .push("gamma")
            .push("alpha")
            .push("beta")
            .push("alpha");
        assert_eq!(s.to_list(), vec![&"alpha", &"beta", &"gamma"]);
    }
}

Deep Comparison

OCaml vs Rust: Functor Comparable Set

Side-by-Side Code

OCaml

module type COMPARABLE = sig
  type t
  val compare : t -> t -> int
end

module MakeSet (C : COMPARABLE) = struct
  type t = C.t list
  let empty = []
  let mem x = List.exists (fun y -> C.compare x y = 0)
  let add x s = if mem x s then s else x :: s
  let to_list s = List.sort C.compare s
end

module IntSet = MakeSet(Int)

let s = IntSet.(empty |> add 3 |> add 1 |> add 3 |> add 2)
(* IntSet.to_list s = [1; 2; 3] *)

Rust (idiomatic — sorted Vec, binary search)

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ComparableSet<T: Ord> {
    items: Vec<T>,
}

impl<T: Ord> ComparableSet<T> {
    pub fn new() -> Self { ComparableSet { items: Vec::new() } }

    pub fn contains(&self, x: &T) -> bool {
        self.items.binary_search(x).is_ok()
    }

    #[must_use]
    pub fn insert(mut self, x: T) -> Self {
        match self.items.binary_search(&x) {
            Ok(_)    => self,
            Err(pos) => { self.items.insert(pos, x); self }
        }
    }

    pub fn to_sorted_vec(&self) -> &[T] { &self.items }
}

let s = ComparableSet::new().insert(3).insert(1).insert(3).insert(2);
// s.to_sorted_vec() == [1, 2, 3]

Rust (functional/recursive — mirrors OCaml list strategy)

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FunctorSet<T: Ord> {
    items: Vec<T>,   // unsorted, mirrors OCaml `C.t list`
}

impl<T: Ord> FunctorSet<T> {
    pub fn new() -> Self { FunctorSet { items: Vec::new() } }

    // OCaml: let mem x = List.exists (fun y -> C.compare x y = 0)
    pub fn mem(&self, x: &T) -> bool {
        self.items.iter().any(|y| y == x)
    }

    // OCaml: let add x s = if mem x s then s else x :: s
    #[must_use]
    pub fn push(mut self, x: T) -> Self {
        if self.mem(&x) { self } else { self.items.push(x); self }
    }

    // OCaml: let to_list s = List.sort C.compare s
    pub fn to_list(&self) -> Vec<&T> {
        let mut v: Vec<&T> = self.items.iter().collect();
        v.sort();
        v
    }
}

Type Signatures

Concept	OCaml	Rust
Module constraint	`module type COMPARABLE`	`T: Ord` trait bound
Functor application	`module IntSet = MakeSet(Int)`	`ComparableSet::<i32>` (monomorphisation)
Set type	`C.t list` (internally)	`Vec<T>`
Membership	`val mem : C.t -> t -> bool`	`fn contains(&self, x: &T) -> bool`
Insert	`val add : C.t -> t -> t`	`fn insert(self, x: T) -> Self`
Sorted view	`val to_list : t -> C.t list`	`fn to_sorted_vec(&self) -> &[T]`

Key Insights

Functor = generic struct: OCaml's MakeSet(C) functor application produces a new module; Rust's monomorphisation of ComparableSet<T> at compile time achieves the same effect — one concrete implementation per element type, zero runtime overhead.

Module type = trait: COMPARABLE specifies type t and val compare : t -> t -> int; Rust's Ord trait encodes exactly this contract (plus PartialOrd), and is already implemented by all numeric primitives and String.

Immutable update style: OCaml's add returns a new t (functional update). The Rust insert(self, ...) -> Self signature consumes the old set and returns a new one, encoding the same ownership discipline without hidden copies.

Performance difference: OCaml's MakeSet stores elements in an arbitrary-order list and pays O(n) on mem and O(n log n) on to_list. The idiomatic Rust ComparableSet maintains sorted order on every insert using binary_search, paying O(n) insert but only O(log n) for contains and O(1) for to_sorted_vec.

Builder chaining: OCaml uses the |> pipe operator (empty |> add 3 |> add 1). Rust replaces this with builder-style method chaining (ComparableSet::new().insert(3).insert(1)), which the #[must_use] attribute enforces so callers cannot accidentally discard the updated set.

When to Use Each Style

**Use idiomatic Rust (ComparableSet):** When you need frequent membership tests or iteration in sorted order — the sorted Vec with binary search gives O(log n) lookups and O(1) sorted iteration with no extra allocation.

**Use functional Rust (FunctorSet):** When faithfully translating OCaml code or teaching the functor-to-generic-struct mapping, and when you want to show the direct line from List.exists/List.sort to their Rust iterator equivalents.

Exercises

Implement fmap for a BTreeSet<T: Ord> by applying a function to each element and collecting results into a new set (note: fmap here is not a true functor due to the Ord constraint — explain why).

Implement a Functor trait for a custom binary tree type and write fmap that applies a function to every leaf value while preserving tree structure.

Implement Functor and fmap for a Result<T, E> type (mapping over the success value only), then compose two fmap calls and verify the functor composition law: fmap(f∘g) == fmap(f) ∘ fmap(g).

Open Source Repos

functional-rust

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

Rust