🦀 Functional Rust

182: Existential Types

Difficulty: 4 Level: Advanced Store values of any type alongside their operations — the type is forgotten, the capability is preserved.

The Problem This Solves

You have values of different types — `i32`, `String`, `f64`, a custom struct — and you want to put them all in one collection. Not as raw bytes; you want to be able to do something with each value, like display it. But you don't want to enumerate all possible types in an enum. An existential type says: "there exists some type T, and I have a value of that T, and T supports these operations." The concrete T is hidden from the outside — only the operations are visible. This is the key idea behind `Box<dyn Trait>`. The contrast with generics: `fn show<T: Display>(v: T)` requires the caller to name `T`. An existential says the callee picks `T` — and nobody needs to name it.

The Intuition

When you write `Box::new(42_i32) as Box<dyn Display>`, you're packing two things into the heap: the value `42` and a pointer to `i32`'s implementation of `Display`. The type `i32` is erased — you can only call `Display`'s methods. This is an existential: some type T implements `Display`, and here's a value of that T. OCaml achieves the same with GADT constructors: `Show : 'a * ('a -> string) -> showable` packs a value with its display function, hiding `'a`. Rust's `Box<dyn Trait>` is the runtime analog with vtable dispatch.

How It Works in Rust

use std::fmt;

// Approach 1: Box<dyn Trait> — Rust's native existential
fn make_showables() -> Vec<Box<dyn fmt::Display>> {
 vec![
     Box::new(42),           // i32 erased — only Display survives
     Box::new("hello"),      // &str erased
     Box::new(3.14),         // f64 erased
 ]
}

for item in make_showables() {
 println!("{}", item);  // dispatch via vtable — correct impl called
}
Approach 2: closure-based packing (mirrors OCaml GADT constructor): 
struct Showable {
 show_fn: Box<dyn Fn() -> String>,
}

impl Showable {
 fn new<T: 'static>(value: T, to_string: fn(&T) -> String) -> Self {
     // Both `value` and `to_string` are captured — T is erased from the outside
     Showable {
         show_fn: Box::new(move || to_string(&value)),
     }
 }

 fn show(&self) -> String { (self.show_fn)() }
}

let items = vec![
 Showable::new(42, |x| x.to_string()),
 Showable::new(String::from("hello"), |x| x.clone()),
 Showable::new(3.14f64, |x| format!("{}", x)),
];
Multi-trait existential via supertrait: 
trait Printable: fmt::Display + fmt::Debug {}
impl<T: fmt::Display + fmt::Debug> Printable for T {}

let items: Vec<Box<dyn Printable>> = vec![Box::new(42), Box::new("hi")];
// Can call both display and debug on each item

What This Unlocks

Key Differences

ConceptOCamlRust
Existential encodingGADT constructor: `Show : 'a * ('a -> string) -> showable``Box<dyn Trait>` via vtable
Closure packing`let pack v f = Show (v, f)``struct { show_fn: Box<dyn Fn() -> String> }`
Multi-capabilityFirst-class module with multiple fieldsSuper-trait combining multiple traits
Recovering TPattern match on GADT constructorNot possible — use `Any::downcast_ref` if needed
AllocationGC-managed heap`Box` — heap allocation, drop via `Drop`
// Example 182: Existential Types
// Hide the concrete type while retaining ability to use it

use std::fmt;

// === Approach 1: Box<dyn Trait> — Rust's native existential ===

fn make_showables() -> Vec<Box<dyn fmt::Display>> {
    vec![
        Box::new(42),
        Box::new("hello"),
        Box::new(3.14),
        Box::new(true),
    ]
}

// === Approach 2: Custom existential with closure (like OCaml GADT) ===

struct Showable {
    show_fn: Box<dyn Fn() -> String>,
}

impl Showable {
    fn new<T: 'static>(value: T, to_string: fn(&T) -> String) -> Self {
        Showable {
            show_fn: Box::new(move || to_string(&value)),
        }
    }

    fn show(&self) -> String {
        (self.show_fn)()
    }
}

// === Approach 3: Existential with comparison ===

struct Comparable {
    compare_fn: Box<dyn Fn() -> std::cmp::Ordering>,
    describe: Box<dyn Fn() -> String>,
}

impl Comparable {
    fn new<T: Ord + fmt::Debug + 'static>(a: T, b: T) -> Self {
        let a2 = format!("{:?}", a);
        let b2 = format!("{:?}", b);
        Comparable {
            compare_fn: Box::new(move || a.cmp(&b)),
            describe: Box::new(move || format!("{} vs {}", a2, b2)),
        }
    }

    fn result(&self) -> &'static str {
        match (self.compare_fn)() {
            std::cmp::Ordering::Less => "less",
            std::cmp::Ordering::Equal => "equal",
            std::cmp::Ordering::Greater => "greater",
        }
    }
}

// Multi-trait existential using a custom trait
trait Printable: fmt::Display + fmt::Debug {}
impl<T: fmt::Display + fmt::Debug> Printable for T {}

fn print_all(items: &[Box<dyn Printable>]) -> Vec<String> {
    items.iter().map(|x| format!("{}", x)).collect()
}

fn main() {
    // Approach 1
    let items = make_showables();
    for item in &items {
        println!("{}", item);
    }

    // Approach 2
    let showables = vec![
        Showable::new(42, |x| x.to_string()),
        Showable::new(String::from("hello"), |x| x.clone()),
        Showable::new(3.14f64, |x| x.to_string()),
    ];
    for s in &showables {
        println!("{}", s.show());
    }

    // Approach 3
    let comparisons = vec![
        Comparable::new(1, 2),
        Comparable::new(5, 5),
        Comparable::new("z", "a"),
    ];
    for c in &comparisons {
        println!("{}: {}", (c.describe)(), c.result());
    }

    println!("✓ All examples running");
}

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

    #[test]
    fn test_box_dyn_display() {
        let items = make_showables();
        assert_eq!(format!("{}", items[0]), "42");
        assert_eq!(format!("{}", items[1]), "hello");
    }

    #[test]
    fn test_custom_showable() {
        let s = Showable::new(42, |x| x.to_string());
        assert_eq!(s.show(), "42");
        let s2 = Showable::new(String::from("world"), |x| x.clone());
        assert_eq!(s2.show(), "world");
    }

    #[test]
    fn test_comparable() {
        assert_eq!(Comparable::new(1, 2).result(), "less");
        assert_eq!(Comparable::new(5, 5).result(), "equal");
        assert_eq!(Comparable::new("z", "a").result(), "greater");
    }

    #[test]
    fn test_multi_trait() {
        let items: Vec<Box<dyn Printable>> = vec![Box::new(42), Box::new("hi")];
        let strs = print_all(&items);
        assert_eq!(strs, vec!["42", "hi"]);
    }
}

(* Example 182: Existential Types *)
(* Hide the concrete type while retaining ability to use it *)

(* Approach 1: Existential via GADT *)
type showable = Show : 'a * ('a -> string) -> showable

let show (Show (x, f)) = f x

let show_list : showable list = [
  Show (42, string_of_int);
  Show ("hello", Fun.id);
  Show (3.14, string_of_float);
  Show (true, string_of_bool);
]

(* Approach 2: First-class module existential *)
module type PRINTABLE = sig
  type t
  val value : t
  val to_string : t -> string
end

let make_printable (type a) (to_s : a -> string) (v : a) : (module PRINTABLE) =
  (module struct
    type t = a
    let value = v
    let to_string = to_s
  end)

let print_it (m : (module PRINTABLE)) =
  let module M = (val m) in
  M.to_string M.value

(* Approach 3: Existential with comparison *)
type comparable = Cmp : 'a * 'a * ('a -> 'a -> int) -> comparable

let compare_pair (Cmp (a, b, cmp)) =
  let r = cmp a b in
  if r < 0 then "less" else if r = 0 then "equal" else "greater"

let () =
  (* Test Approach 1 *)
  let results = List.map show show_list in
  assert (List.nth results 0 = "42");
  assert (List.nth results 1 = "hello");
  assert (List.nth results 3 = "true");

  (* Test Approach 2 *)
  let items = [
    make_printable string_of_int 42;
    make_printable Fun.id "world";
  ] in
  assert (print_it (List.nth items 0) = "42");
  assert (print_it (List.nth items 1) = "world");

  (* Test Approach 3 *)
  assert (compare_pair (Cmp (1, 2, compare)) = "less");
  assert (compare_pair (Cmp (5, 5, compare)) = "equal");
  assert (compare_pair (Cmp ("z", "a", String.compare)) = "greater");

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 182 — Existential Types

Basic Existential

OCaml

🐪 Show OCaml equivalent
type showable = Show : 'a * ('a -> string) -> showable

let show (Show (x, f)) = f x

let items = [Show (42, string_of_int); Show ("hello", Fun.id)]
let results = List.map show items

Rust

let items: Vec<Box<dyn fmt::Display>> = vec![Box::new(42), Box::new("hello")];
let results: Vec<String> = items.iter().map(|x| format!("{}", x)).collect();

Closure-Based Existential

OCaml

🐪 Show OCaml equivalent
type showable = Show : 'a * ('a -> string) -> showable

Rust

struct Showable {
 show_fn: Box<dyn Fn() -> String>,
}

impl Showable {
 fn new<T: 'static>(value: T, to_string: fn(&T) -> String) -> Self {
     Showable { show_fn: Box::new(move || to_string(&value)) }
 }
}

First-Class Module vs Super-Trait

OCaml

🐪 Show OCaml equivalent
module type PRINTABLE = sig
type t
val value : t
val to_string : t -> string
end

let print_it (m : (module PRINTABLE)) =
let module M = (val m) in M.to_string M.value

Rust

trait Printable: fmt::Display + fmt::Debug {}
impl<T: fmt::Display + fmt::Debug> Printable for T {}

fn print_all(items: &[Box<dyn Printable>]) -> Vec<String> {
 items.iter().map(|x| format!("{}", x)).collect()
}

Related Examples

#181 181: Type-Safe SQL-Like Query Builder 🌱 #183 183: Heterogeneous Vec with Safe Downcast 🌱 #179 179: GADT Preventing Runtime Errors 🌱 #178 178: Length-Indexed Lists 🌱
All Examples