136 Expert

Existential Types

Functional Programming

Tutorial

The Problem

An existential type says: "there exists some concrete type implementing this interface, but I won't tell you which one." This enables hiding implementation details, building heterogeneous collections (a list of values with different concrete types all sharing a common interface), and returning values whose concrete type is unnameable (like closures). Existential types are the dual of universal (generic) types, and they appear in every major typed language under different names.

🎯 Learning Outcomes

• Understand what an existential type is and how it differs from a generic (universal) type

• Learn Rust's two encodings: impl Trait (static, zero-cost) and Box<dyn Trait> (dynamic, heap-allocated)

• See when each encoding is appropriate: single opaque return vs. heterogeneous collection

• Connect Rust's existential types to OCaml's first-class modules and GADTs

Code Example

pub trait Showable { fn show(&self) -> String; }

// Caller sees `impl Showable`; concrete type `Counter` is hidden at the API boundary.
pub fn make_counter(n: u32) -> impl Showable { Counter(n) }

module type SHOWABLE = sig
  type t
  val value : t
  val show  : t -> string
end

let pack_showable (type a) (show : a -> string) (value : a) : (module SHOWABLE) =
  (module struct
    type t = a
    let value = value
    let show  = show
  end)

let show_it (m : (module SHOWABLE)) =
  let module M = (val m) in M.show M.value

Key Differences

Two encodings: Rust provides static existentials (impl Trait) and dynamic existentials (Box<dyn Trait>); OCaml uses first-class modules and GADTs for both.

Vtable layout: Rust's dyn Trait vtable is fixed at trait definition time; OCaml's GADT-based existentials pack arbitrary functions without a fixed interface.

Collection use: Only Box<dyn Trait> (dynamic) allows heterogeneous collections; OCaml's showable list works the same way with GADT encoding.

Dyn compatibility: Rust imposes dyn-compatibility rules (no generic methods); OCaml's approach has no such restriction.

OCaml Approach

OCaml encodes existential types via first-class modules:

module type SHOWABLE = sig type t val show : t -> string end
type showable = (module SHOWABLE with type t = _)
(* or via GADTs: *)
type showable = Show : 'a * ('a -> string) -> showable

The GADT encoding packs the value and its show function together, erasing the concrete type. This is more flexible than Rust's dyn Trait because the packed function is not restricted to a fixed vtable layout.

Full Source

#![allow(clippy::all)]
//! Example 136: Existential Types
//!
//! Rust encodes existential types in two complementary ways:
//!   - `impl Trait` in return position: opaque, zero-cost, single concrete type per call-site
//!   - `Box<dyn Trait>` / `dyn Trait`: runtime dispatch, heterogeneous collections
//!
//! OCaml uses first-class modules and GADTs to achieve the same hiding of the
//! concrete type behind an interface.

// ---------------------------------------------------------------------------
// Shared trait — the "interface" callers know about
// ---------------------------------------------------------------------------

/// Something that can produce a human-readable string.
pub trait Showable {
    fn show(&self) -> String;
}

// ---------------------------------------------------------------------------
// Concrete implementations (hidden from callers behind the existential)
// ---------------------------------------------------------------------------

struct Counter(u32);

impl Showable for Counter {
    fn show(&self) -> String {
        format!("counter({})", self.0)
    }
}

struct Label(String);

impl Showable for Label {
    fn show(&self) -> String {
        format!("label({:?})", self.0)
    }
}

impl Showable for i32 {
    fn show(&self) -> String {
        format!("i32({})", self)
    }
}

impl Showable for f64 {
    fn show(&self) -> String {
        format!("f64({:.2})", self)
    }
}

// ---------------------------------------------------------------------------
// Approach 1: `impl Trait` — opaque return type (static existential)
//
// The caller knows *some* Showable is returned; the concrete type is erased.
// All branches must return the *same* concrete type — chosen at compile time.
// ---------------------------------------------------------------------------

/// Returns a `Counter` wrapped as an opaque `impl Showable`.
/// Caller sees only the `Showable` interface; `Counter` is hidden.
pub fn make_counter(n: u32) -> impl Showable {
    Counter(n)
}

/// Returns a `Label` wrapped as an opaque `impl Showable`.
pub fn make_label(s: &str) -> impl Showable {
    Label(s.to_owned())
}

// ---------------------------------------------------------------------------
// Approach 2: `Box<dyn Trait>` — dynamic existential
//
// Analogous to OCaml's `(module SHOWABLE)` packing: the concrete type is
// erased at runtime. Enables heterogeneous collections and runtime dispatch.
// ---------------------------------------------------------------------------

/// Pack any `Showable + 'static` into an erased `Box<dyn Showable>`.
/// This mirrors OCaml's `pack_showable`: both hide the concrete type `T`.
pub fn pack(value: impl Showable + 'static) -> Box<dyn Showable> {
    Box::new(value)
}

/// Show every item in a heterogeneous collection of erased showables.
/// Mirrors OCaml's `show_any_list` over `any_list` (GADT existential).
pub fn show_all(items: &[Box<dyn Showable>]) -> Vec<String> {
    items.iter().map(|item| item.show()).collect()
}

// ---------------------------------------------------------------------------
// Approach 3: closure-based erasure (OCaml `{ show : unit -> string }`)
//
// Store only the *behaviour*, not the value. The concrete type disappears
// the moment the closure captures it — identical to OCaml's record approach.
// ---------------------------------------------------------------------------

/// An erased "showable" that owns just the behaviour, not the value.
pub struct ShowClosure {
    show_fn: Box<dyn Fn() -> String>,
}

impl ShowClosure {
    /// Capture `value` and `show_fn` into a closure; the type `T` is erased.
    pub fn new<T>(value: T, show_fn: impl Fn(&T) -> String + 'static) -> Self
    where
        T: 'static,
    {
        ShowClosure {
            show_fn: Box::new(move || show_fn(&value)),
        }
    }

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

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

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

    #[test]
    fn test_impl_trait_counter() {
        let s = make_counter(7);
        assert_eq!(s.show(), "counter(7)");
    }

    #[test]
    fn test_impl_trait_label() {
        let s = make_label("hello");
        assert_eq!(s.show(), "label(\"hello\")");
    }

    #[test]
    fn test_dyn_trait_heterogeneous_collection() {
        // A Vec that holds i32, f64, Counter, Label — all erased to Box<dyn Showable>
        let items: Vec<Box<dyn Showable>> = vec![
            pack(42i32),
            pack(3.14f64),
            pack(Counter(99)),
            pack(Label("rust".to_owned())),
        ];

        let shown = show_all(&items);
        assert_eq!(shown[0], "i32(42)");
        assert_eq!(shown[1], "f64(3.14)");
        assert_eq!(shown[2], "counter(99)");
        assert_eq!(shown[3], "label(\"rust\")");
    }

    #[test]
    fn test_closure_erasure_hides_type() {
        // The integer `42` is captured; the type `i32` is completely hidden.
        let s = ShowClosure::new(42i32, |n| format!("the answer is {}", n));
        assert_eq!(s.show(), "the answer is 42");
    }

    #[test]
    fn test_closure_erasure_with_struct() {
        let s = ShowClosure::new(Counter(5), |c| c.show());
        assert_eq!(s.show(), "counter(5)");
    }

    #[test]
    fn test_show_all_empty() {
        let items: Vec<Box<dyn Showable>> = vec![];
        assert_eq!(show_all(&items), Vec::<String>::new());
    }
}

(* Example 136: Existential Types *)

(* Approach 1: Existential via first-class modules *)
module type SHOWABLE = sig
  type t
  val value : t
  val show : t -> string
end

let pack_showable (type a) (show : a -> string) (value : a) : (module SHOWABLE) =
  (module struct
    type t = a
    let value = value
    let show = show
  end)

let show_it (m : (module SHOWABLE)) =
  let module M = (val m) in M.show M.value

(* Approach 2: Existential via closure/record *)
type showable = { show : unit -> string }

let make_showable show value = { show = fun () -> show value }

(* Approach 3: GADT existential *)
type any_list = AnyList : 'a list * ('a -> string) -> any_list

let show_any_list (AnyList (lst, show)) =
  String.concat ", " (List.map show lst)

(* Tests *)
let () =
  let items = [
    pack_showable string_of_int 42;
    pack_showable (fun s -> s) "hello";
    pack_showable string_of_float 3.14;
  ] in
  let results = List.map show_it items in
  assert (results = ["42"; "hello"; "3.14"]);

  let items2 = [
    make_showable string_of_int 42;
    make_showable (fun s -> s) "hello";
  ] in
  assert ((List.hd items2).show () = "42");

  let al = AnyList ([1;2;3], string_of_int) in
  assert (show_any_list al = "1, 2, 3");

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_impl_trait_counter() {
        let s = make_counter(7);
        assert_eq!(s.show(), "counter(7)");
    }

    #[test]
    fn test_impl_trait_label() {
        let s = make_label("hello");
        assert_eq!(s.show(), "label(\"hello\")");
    }

    #[test]
    fn test_dyn_trait_heterogeneous_collection() {
        // A Vec that holds i32, f64, Counter, Label — all erased to Box<dyn Showable>
        let items: Vec<Box<dyn Showable>> = vec![
            pack(42i32),
            pack(3.14f64),
            pack(Counter(99)),
            pack(Label("rust".to_owned())),
        ];

        let shown = show_all(&items);
        assert_eq!(shown[0], "i32(42)");
        assert_eq!(shown[1], "f64(3.14)");
        assert_eq!(shown[2], "counter(99)");
        assert_eq!(shown[3], "label(\"rust\")");
    }

    #[test]
    fn test_closure_erasure_hides_type() {
        // The integer `42` is captured; the type `i32` is completely hidden.
        let s = ShowClosure::new(42i32, |n| format!("the answer is {}", n));
        assert_eq!(s.show(), "the answer is 42");
    }

    #[test]
    fn test_closure_erasure_with_struct() {
        let s = ShowClosure::new(Counter(5), |c| c.show());
        assert_eq!(s.show(), "counter(5)");
    }

    #[test]
    fn test_show_all_empty() {
        let items: Vec<Box<dyn Showable>> = vec![];
        assert_eq!(show_all(&items), Vec::<String>::new());
    }
}

Deep Comparison

OCaml vs Rust: Existential Types

Side-by-Side Code

OCaml — first-class module packing

module type SHOWABLE = sig
  type t
  val value : t
  val show  : t -> string
end

let pack_showable (type a) (show : a -> string) (value : a) : (module SHOWABLE) =
  (module struct
    type t = a
    let value = value
    let show  = show
  end)

let show_it (m : (module SHOWABLE)) =
  let module M = (val m) in M.show M.value

OCaml — closure record (lighter weight)

type showable = { show : unit -> string }

let make_showable show value = { show = fun () -> show value }

Rust — `impl Trait` (static existential, zero-cost)

pub trait Showable { fn show(&self) -> String; }

// Caller sees `impl Showable`; concrete type `Counter` is hidden at the API boundary.
pub fn make_counter(n: u32) -> impl Showable { Counter(n) }

Rust — `Box<dyn Trait>` (dynamic existential, heterogeneous collections)

// Erase the concrete type at runtime; enable Vec<Box<dyn Showable>>.
pub fn pack(value: impl Showable + 'static) -> Box<dyn Showable> { Box::new(value) }
pub fn show_all(items: &[Box<dyn Showable>]) -> Vec<String> {
    items.iter().map(|i| i.show()).collect()
}

Rust — closure-based erasure (mirrors OCaml's record approach)

pub struct ShowClosure { show_fn: Box<dyn Fn() -> String> }

impl ShowClosure {
    pub fn new<T: 'static>(value: T, show_fn: impl Fn(&T) -> String + 'static) -> Self {
        ShowClosure { show_fn: Box::new(move || show_fn(&value)) }
    }
    pub fn show(&self) -> String { (self.show_fn)() }
}

Type Signatures

Concept	OCaml	Rust
Existential return	`(module SHOWABLE)`	`impl Showable`
Runtime-erased value	`{ show : unit -> string }`	`Box<dyn Showable>`
Closure erasure	`make_showable : ('a -> string) -> 'a -> showable`	`ShowClosure::new<T>(T, Fn(&T)->String)`
Heterogeneous list	`any_list` GADT	`Vec<Box<dyn Showable>>`
Interface declaration	`module type SHOWABLE`	`trait Showable`

Key Insights

Two flavours of existential: Rust offers impl Trait (static, compiler-resolved, zero overhead) and Box<dyn Trait> (dynamic, vtable dispatch). OCaml's first-class modules sit between these: they carry type information but erase the concrete identity from callers.

Static vs dynamic dispatch: impl Trait in return position is monomorphised by the compiler — no allocation, no vtable. Box<dyn Trait> pays one allocation and one indirection per call. OCaml's (module SHOWABLE) is dynamically dispatched like dyn Trait.

Closure erasure is identical in spirit: OCaml's { show : unit -> string } and Rust's Box<dyn Fn() -> String> both capture a value and erase its type by closing over it. The only difference is syntactic.

**impl Trait forces a single concrete type per function**: if you need to return different concrete types at runtime, you must use Box<dyn Trait>. OCaml's first-class modules always allow heterogeneous unpacking because the module itself carries the type index.

**Lifetime annotation 'static**: Rust requires T: 'static when boxing a trait object that might outlive the call frame. OCaml's GC-managed heap makes this bookkeeping invisible, though the same guarantee is implicitly enforced at runtime.

When to Use Each Style

**Use impl Trait when:** the function always returns the same concrete type and you just want to hide it from the public API — zero-cost abstraction.

**Use Box<dyn Trait> when:** you need a heterogeneous collection, a function that returns different types depending on runtime state, or you're building a plugin/registry system.

**Use closure erasure (ShowClosure) when:** you want to bundle a value with custom behaviour at the point of construction — closest to OCaml's record-based existential and the most flexible approach.

Exercises

Create a Vec<Box<dyn Display>> containing an i32, a f64, and a String, then print each element.

Implement make_counter() -> impl FnMut() -> u32 using a closure as a static existential, hiding the closure type.

Write a plugin registry that accepts Box<dyn Plugin> values from external code and calls their run method polymorphically.

Open Source Repos

functional-rust

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

Rust