260: Functor Comparable Set

Difficulty: 3 Level: Advanced Build a generic ordered set for any comparable type — OCaml's `Set.Make` functor translated to Rust generics.

The Problem This Solves

OCaml's standard library doesn't have a single polymorphic set type. Instead, you use a functor: `Set.Make(Int)` produces an `IntSet` module; `Set.Make(String)` produces a `StringSet` module. Each is a separate type with its own `empty`, `add`, `mem`, and `to_list`. The functor takes a module that provides a comparison function and returns a full set implementation. This is a design choice: the functor captures comparison at the type level, enabling the compiler to verify that elements are comparable before any runtime code runs. The trade-off is that you can't write a function that works on any set — you'd need a functor parameter. In Rust, generic structs with trait bounds achieve the same guarantee at compile time. `ComparableSet<T: Ord>` works for any type that implements `Ord` — integers, strings, custom structs with `#[derive(Ord)]` — without creating separate types. Monomorphisation generates specialized code per type, identical to what OCaml's functor produces.

The Intuition

A comparable set is a sorted, deduplicated collection. "Comparable" means elements have a total ordering — you can say whether any element is less than, equal to, or greater than any other. Without that guarantee, you can't maintain sorted order. OCaml enforces this via the `COMPARABLE` module type: the functor refuses to compile if the argument module doesn't provide `compare`. Rust enforces it via the `Ord` trait bound: the compiler refuses to instantiate `ComparableSet<T>` if `T` doesn't implement `Ord`. The sorted `Vec` representation gives O(log n) membership via `binary_search` — better than OCaml's list-based version which scans linearly. Insert maintains sorted order by finding the correct position before inserting.

How It Works in Rust

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

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

 // O(log n) membership test via binary search
 pub fn contains(&self, x: &T) -> bool {
     self.items.binary_search(x).is_ok()
 }

 // Consume self, return new set with x inserted (or unchanged if duplicate)
 #[must_use]
 pub fn insert(mut self, x: T) -> Self {
     match self.items.binary_search(&x) {
         Ok(_) => self,            // already present — deduplicate
         Err(pos) => {
             self.items.insert(pos, x);  // insert at sorted position
             self
         }
     }
 }

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

// Usage — works for any Ord type, no module boilerplate
let int_set = ComparableSet::new().insert(3).insert(1).insert(4).insert(1).insert(5);
// → [1, 3, 4, 5]  (sorted, deduplicated)

let str_set = ComparableSet::new().insert("fox").insert("cat").insert("ant");
// → ["ant", "cat", "fox"]

The builder pattern (`insert` consumes `self` and returns `Self`) mirrors OCaml's immutable-update semantics while staying idiomatic Rust.

What This Unlocks

Type-safe generic collections — one `ComparableSet<T>` works for any ordered type; no code duplication across element types.
Understanding OCaml functors — this example makes the OCaml functor pattern concrete: trait bounds are the Rust equivalent of `COMPARABLE` module types.
Sorted containers — the sorted-Vec pattern (binary_search + insert at position) applies to priority queues, deduplication, and ordered caches.

Key Differences

Concept	OCaml	Rust
Abstraction mechanism	Functor: `MakeSet(Int)` → new module	Generic: `ComparableSet<i32>` — monomorphised
Comparable constraint	Module type `COMPARABLE` with `compare`	`Ord` trait — already implemented by primitives
Membership test	`List.exists` O(n) (OCaml list version)	`binary_search` O(log n)
Insert	Returns new value (functional)	Consumes `self`, returns `Self`
Separate types	`IntSet` ≠ `StringSet` — distinct modules	Same type `ComparableSet<T>` — different monomorphisations

// Solution 1: Idiomatic Rust — sorted Vec with binary search, Ord trait bound
#[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> {
    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
    }

    pub fn len(&self) -> usize {
        self.items.len()
    }

    pub fn is_empty(&self) -> bool {
        self.items.is_empty()
    }
}

// Solution 2: OCaml-style functional — unsorted Vec, sort on to_list
#[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() }
    }

    pub fn mem(&self, x: &T) -> bool {
        self.items.iter().any(|y| y == x)
    }

    #[must_use]
    pub fn push(mut self, x: T) -> Self {
        if self.mem(&x) {
            self
        } else {
            self.items.push(x);
            self
        }
    }

    pub fn to_list(&self) -> Vec<&T> {
        let mut sorted: Vec<&T> = self.items.iter().collect();
        sorted.sort();
        sorted
    }
}

fn main() {
    // ComparableSet — idiomatic, sorted on insertion
    let int_set = ComparableSet::new()
        .insert(3)
        .insert(1)
        .insert(3) // duplicate
        .insert(2);
    println!("ComparableSet integers: {:?}", int_set.to_sorted_vec());
    println!("contains(1): {}", int_set.contains(&1));
    println!("contains(5): {}", int_set.contains(&5));

    let str_set = ComparableSet::new()
        .insert("banana")
        .insert("apple")
        .insert("cherry")
        .insert("apple"); // duplicate
    println!("ComparableSet strings:  {:?}", str_set.to_sorted_vec());

    // FunctorSet — OCaml-style, mirrors: IntSet.(empty |> add 3 |> add 1 |> add 3 |> add 2)
    let fs = FunctorSet::new().push(3).push(1).push(3).push(2);
    let sorted: Vec<_> = fs.to_list();
    println!("FunctorSet to_list:     {:?}", sorted);
}

/* Output:
   ComparableSet integers: [1, 2, 3]
   contains(1): true
   contains(5): false
   ComparableSet strings:  ["apple", "banana", "cherry"]
   FunctorSet to_list:     [1, 2, 3]
*/

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

    #[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).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");
        assert_eq!(s.len(), 3);
        assert_eq!(s.to_sorted_vec(), &["apple", "banana", "cherry"]);
    }

    #[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);
        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() {
        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"

📊 Detailed Comparison

OCaml vs Rust: Functor Comparable Set

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

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

1. 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. 2. 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`. 3. 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. 4. 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`. 5. 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.