136: Existential Types

Difficulty: ⭐⭐⭐ Level: Advanced Hide a concrete type behind a trait so callers can use the behavior without knowing the implementation — the type exists, but its identity is secret.

The Problem This Solves

You're writing a function that returns "something you can display." The caller doesn't care if it's an `i32` or a `String` or a custom struct — they just want to call `.show()`. But Rust's type system is explicit: a function must declare its exact return type. You can't just return "some type that implements `Showable`" without either naming the concrete type (breaking abstraction) or paying the cost of a `Box<dyn Trait>`. Or you have a collection that needs to hold values of different types — integers, strings, floats — all behind the same interface. A `Vec<Box<dyn Display>>` works, but where's the documentation pattern? How do you communicate "this is the existential idiom" to readers? Existential types are the formal name for what Rust calls `impl Trait` (for opaque return types) and `dyn Trait` (for trait objects). Both say: "there exists some concrete type here — you can use it through this trait interface, but you don't need to know what it is."

The Intuition

The word "existential" comes from logic: "there exists a type T such that T implements Showable." The caller doesn't know which T — just that one exists, and they can use the `Showable` interface on it. In practice:

`-> impl Showable`: "I return some showable thing. It's always the same concrete type, but I'm not telling you what it is." Faster (no indirection), but inflexible — all branches must return the same concrete type.
`-> Box<dyn Showable>`: "I return some showable thing. It might be different each time." Flexible (heterogeneous), costs one heap allocation and one pointer dereference.

The closure-based variant captures a value and a display function together, hiding the type even more completely — you don't even need a trait impl on the original type.

How It Works in Rust

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

// impl Trait: opaque return — caller sees Showable interface, not i32
// Limitation: all branches MUST return the same concrete type
fn make_thing() -> impl Showable {
 42i32   // always i32, but caller just sees "some Showable"
}

// Box<dyn Trait>: dynamic dispatch — can return different types per branch
fn make_showable_dyn(choice: u8) -> Box<dyn Showable> {
 match choice {
     0 => Box::new(42i32),              // i32
     1 => Box::new("hello".to_string()), // String
     _ => Box::new(3.14f64),            // f64
 }
}

// Heterogeneous collection — all items behind the same trait interface
let items: Vec<Box<dyn Showable>> = vec![
 Box::new(42i32),
 Box::new("hello".to_string()),
 Box::new(3.14f64),
];
let strings: Vec<String> = items.iter().map(|item| item.show()).collect();
// ["42", "hello", "3.14"]

// Closure-based variant: pack a value and its display logic together
// The concrete type T is completely hidden — not even a trait is needed on T
struct ShowableBox {
 show_fn: Box<dyn Fn() -> String>,
}

impl ShowableBox {
 fn new<T: 'static>(value: T, show: impl Fn(&T) -> String + 'static) -> Self {
     ShowableBox {
         show_fn: Box::new(move || show(&value)),  // T is captured and hidden
     }
 }
 fn show(&self) -> String { (self.show_fn)() }
}

let box1 = ShowableBox::new(42, |x| format!("{}", x));
let box2 = ShowableBox::new("hello", |s| s.to_string());
// box1 and box2 have the same type ShowableBox, but hide different concrete types

What This Unlocks

Plugin systems — load plugins as `Box<dyn Plugin>` collections; each plugin's concrete type is unknown to the host, but the interface is uniform.
Iterator composition — `impl Iterator<Item = T>` return types let you compose lazy iterators without exposing complex nested types like `Map<Filter<Vec<T>>>`.
Strategy pattern — store different algorithms (`Box<dyn Sorter>`, `Box<dyn Renderer>`) without a top-level enum, keeping extension open.

Key Differences

Concept	OCaml	Rust
Existential packing	`pack (type a) show value : (module SHOWABLE)` — first-class module	`Box::new(value) as Box<dyn Trait>` — heap allocation
Opaque return	Module signature hiding `type t`	`-> impl Trait` — same concrete type, hidden
Heterogeneous	`(module SHOWABLE) list`	`Vec<Box<dyn Trait>>`
Closure existential	Closures capture type implicitly	`Box<dyn Fn()>` erases closure type

// Example 136: Existential Types
// Rust uses `impl Trait` (opaque return) and trait objects for existential types

// Approach 1: impl Trait as existential return type
trait Showable: std::fmt::Debug {
    fn show(&self) -> String;
}

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

// Existential return — caller doesn't know concrete type
fn make_showable(choice: u8) -> impl Showable {
    // Note: all branches must return the same concrete type with impl Trait
    // For truly heterogeneous returns, use Box<dyn Showable>
    match choice {
        _ => 42i32,
    }
}

// Approach 2: Trait objects as existential (heterogeneous)
fn make_showable_dyn(choice: u8) -> Box<dyn Showable> {
    match choice {
        0 => Box::new(42i32),
        1 => Box::new("hello".to_string()),
        _ => Box::new(3.14f64),
    }
}

fn show_all(items: &[Box<dyn Showable>]) -> Vec<String> {
    items.iter().map(|item| item.show()).collect()
}

// Approach 3: Existential via closure (like OCaml record approach)
struct ShowableBox {
    show_fn: Box<dyn Fn() -> String>,
}

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

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

// Existential with iteration
struct AnyIter {
    items: Box<dyn Iterator<Item = String>>,
}

impl AnyIter {
    fn from_iter<I: Iterator<Item = String> + 'static>(iter: I) -> Self {
        AnyIter { items: Box::new(iter) }
    }

    fn collect_vec(self) -> Vec<String> {
        self.items.collect()
    }
}

fn main() {
    // Trait object existentials
    let items: Vec<Box<dyn Showable>> = vec![
        Box::new(42i32),
        Box::new("hello".to_string()),
        Box::new(3.14f64),
    ];
    println!("Shown: {:?}", show_all(&items));

    // Closure-based existentials
    let boxes = vec![
        ShowableBox::new(42, |x| format!("{}", x)),
        ShowableBox::new("hello", |x| x.to_string()),
        ShowableBox::new(3.14, |x| format!("{:.2}", x)),
    ];
    for b in &boxes {
        println!("ShowableBox: {}", b.show());
    }

    // impl Trait return
    let s = make_showable(0);
    println!("impl Showable: {}", s.show());
}

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

    #[test]
    fn test_trait_object_existential() {
        let items: Vec<Box<dyn Showable>> = vec![
            Box::new(42i32),
            Box::new("test".to_string()),
        ];
        let shown = show_all(&items);
        assert_eq!(shown, vec!["42", "test"]);
    }

    #[test]
    fn test_showable_box() {
        let b = ShowableBox::new(42, |x| format!("{}", x));
        assert_eq!(b.show(), "42");
    }

    #[test]
    fn test_make_showable_dyn() {
        let s = make_showable_dyn(0);
        assert_eq!(s.show(), "42");
        let s = make_showable_dyn(1);
        assert_eq!(s.show(), "hello");
    }

    #[test]
    fn test_any_iter() {
        let iter = AnyIter::from_iter(vec!["a".to_string(), "b".to_string()].into_iter());
        assert_eq!(iter.collect_vec(), vec!["a", "b"]);
    }

    #[test]
    fn test_impl_trait_return() {
        let s = make_showable(0);
        assert_eq!(s.show(), "42");
    }
}

(* 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"

📊 Detailed Comparison

Comparison: Existential Types

OCaml

🐪 Show OCaml equivalent

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

let pack (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 = let module M = (val m) in M.show M.value

Rust

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

// Heterogeneous collection (existential)
let items: Vec<Box<dyn Showable>> = vec![
 Box::new(42i32),
 Box::new("hello".to_string()),
];

// Opaque return (existential)
fn make_thing() -> impl Showable { 42i32 }