179: GADT Preventing Runtime Errors

Difficulty: ⭐⭐⭐ Level: Advanced Encode emptiness/non-emptiness in a list's type so that `head` on an empty list is a compile-time error instead of a runtime panic.

The Problem This Solves

Every Rust developer has written `vec.first().unwrap()` with a mental note "this can't be empty here." Sometimes you're right. Sometimes a refactor later breaks the invariant, and you get a panic in production at 2 AM. The type system never helped you — `Vec<T>` has no memory of whether it was just created empty or has been filled. The real problem is that the guarantee "this list is non-empty" lives in your head, in comments, maybe in a test — but not in the type. When code changes, the guarantee drifts silently. Phantom types let you bake the guarantee into the type itself: `SafeList<T, NonEmpty>` vs `SafeList<T, Empty>`. The `head` method only exists on the `NonEmpty` variant — the compiler simply won't let you call it on an empty list. This is a specific application of the type-state pattern (see example 180 for the general form). Here the "state" being tracked is a structural property of the data itself: does it have at least one element?

The Intuition

A coffee machine has two states: "has coffee" and "empty." The "dispense" button only works in the "has coffee" state — it's physically locked out otherwise. You don't check at runtime whether there's coffee; the machine's state tells you. If you want to dispense, you must first be holding a `Machine<HasCoffee>`, not a `Machine<Empty>`. A `SafeList<T, NonEmpty>` works the same way. `head` is only defined on `SafeList<T, NonEmpty>`. To get a `NonEmpty` list, you must either start with a `cons` operation (which is always non-empty) or branch based on what you have. The emptiness state is tracked at every step.

How It Works in Rust

use std::marker::PhantomData;

// Type-level state tags — no data, just markers
struct Empty;
struct NonEmpty;

// The list itself — S is the phantom state
struct SafeList<T, S> {
 data: Vec<T>,
 _state: PhantomData<S>,
}

// Empty constructor — only produces Empty
impl<T> SafeList<T, Empty> {
 fn new() -> Self {
     SafeList { data: Vec::new(), _state: PhantomData }
 }
}

// Pushing an element always produces NonEmpty, regardless of prior state
impl<T, S> SafeList<T, S> {
 fn push(mut self, val: T) -> SafeList<T, NonEmpty> {
     self.data.push(val);
     SafeList { data: self.data, _state: PhantomData }
 }
}

// head only exists for NonEmpty lists — Empty lists literally have no head method
impl<T> SafeList<T, NonEmpty> {
 fn head(&self) -> &T {
     &self.data[0]   // safe — we know it's non-empty by type
 }
}

// Correct usage:
let empty: SafeList<i32, Empty> = SafeList::new();
let nonempty: SafeList<i32, NonEmpty> = empty.push(42);
println!("{}", nonempty.head()); // ✓ compiles

// This fails to compile:
// let empty: SafeList<i32, Empty> = SafeList::new();
// empty.head(); // error: method not found in `SafeList<i32, Empty>`

The `head` method doesn't exist on `SafeList<T, Empty>` — not "it exists but checks at runtime," but literally doesn't exist in that `impl` block. The compiler catches the mistake before the program runs.

What This Unlocks

Queue/deque operations — `dequeue` only available on a `Queue<NonEmpty>`, eliminating a whole class of defensive checks.
Parsing combinators — a match result that carries whether it consumed any input, used to detect infinite loops in grammars at compile time.
Resource protocols — file handles, database cursors, anything that must be populated before reading; the "has data" state is tracked in the type.

Key Differences

Concept	OCaml	Rust
Mechanism	GADT constructors: `SNil : ('a, empty) safe_list` vs `SCons : 'a * ... -> ('a, nonempty) safe_list`	`PhantomData<Empty>` vs `PhantomData<NonEmpty>` with separate `impl` blocks
Pattern matching	Compiler knows `SCons` branch is `nonempty`; `SNil` branch in `safe_head` is exhaustively impossible	No match-level type refinement; safety enforced by only having methods on one impl block
State transition on push	Implicit via constructor choice	Explicit: `push` consumes `SafeList<T, S>` and returns `SafeList<T, NonEmpty>`
Ergonomics	Natural in GADT pattern matching	Method-based API; transitions clear from signatures
Zero-cost	Yes	Yes — PhantomData has no runtime representation

// Example 179: GADT Preventing Runtime Errors — Safe Head
// Type-level guarantees that head can never be called on an empty list

use std::marker::PhantomData;

// === Approach 1: Phantom type states for emptiness ===

struct Empty;
struct NonEmpty;

struct SafeList<T, S> {
    data: Vec<T>,
    _state: PhantomData<S>,
}

impl<T> SafeList<T, Empty> {
    fn new() -> Self {
        SafeList { data: Vec::new(), _state: PhantomData }
    }

    // Pushing to empty list transitions to NonEmpty
    fn push(mut self, val: T) -> SafeList<T, NonEmpty> {
        self.data.push(val);
        SafeList { data: self.data, _state: PhantomData }
    }
}

impl<T> SafeList<T, NonEmpty> {
    // head is ONLY available on NonEmpty lists
    fn head(&self) -> &T {
        &self.data[0]
    }

    fn tail(&self) -> &[T] {
        &self.data[1..]
    }

    fn push(mut self, val: T) -> SafeList<T, NonEmpty> {
        self.data.push(val);
        self
    }

    fn to_vec(&self) -> &Vec<T> {
        &self.data
    }
}

// Construct from a known non-empty source
fn from_vec<T>(v: Vec<T>) -> Option<SafeList<T, NonEmpty>> {
    if v.is_empty() {
        None
    } else {
        Some(SafeList { data: v, _state: PhantomData })
    }
}

// === Approach 2: NonEmpty struct (like OCaml NonEmpty module) ===

#[derive(Debug, Clone)]
struct NonEmptyVec<T> {
    head: T,
    tail: Vec<T>,
}

impl<T> NonEmptyVec<T> {
    fn new(head: T, tail: Vec<T>) -> Self {
        NonEmptyVec { head, tail }
    }

    fn from_vec(v: Vec<T>) -> Option<Self> {
        let mut iter = v.into_iter();
        iter.next().map(|head| NonEmptyVec {
            head,
            tail: iter.collect(),
        })
    }

    fn head(&self) -> &T {
        &self.head
    }

    fn tail(&self) -> &[T] {
        &self.tail
    }

    fn to_vec(&self) -> Vec<&T> {
        let mut v = vec![&self.head];
        v.extend(self.tail.iter());
        v
    }

    fn map<U>(&self, f: impl Fn(&T) -> U) -> NonEmptyVec<U> {
        NonEmptyVec {
            head: f(&self.head),
            tail: self.tail.iter().map(f).collect(),
        }
    }

    fn fold<U>(&self, init: U, f: impl Fn(U, &T) -> U) -> U {
        let acc = f(init, &self.head);
        self.tail.iter().fold(acc, f)
    }
}

// === Approach 3: Type-state with const generics ===
// Using const generics to guarantee non-empty at type level

struct StaticList<T, const N: usize> {
    data: [T; N],
}

// head only exists when N >= 1
impl<T, const N: usize> StaticList<T, N> {
    fn head(&self) -> &T {
        &self.data[0]
    }

    fn len(&self) -> usize {
        N
    }
}

// Cannot create StaticList<T, 0> with this constructor
fn static_list<T, const N: usize>(data: [T; N]) -> StaticList<T, N> {
    StaticList { data }
}

fn main() {
    // Approach 1: Type-state
    let list = SafeList::<i32, Empty>::new()
        .push(1)
        .push(2)
        .push(3);
    println!("head = {}", list.head());
    println!("tail = {:?}", list.tail());

    // This won't compile:
    // let empty = SafeList::<i32, Empty>::new();
    // empty.head(); // Error: no method `head` on SafeList<i32, Empty>

    // Approach 2: NonEmpty struct
    let ne = NonEmptyVec::new(1, vec![2, 3]);
    println!("head = {}", ne.head());
    let doubled = ne.map(|x| x * 2);
    println!("doubled head = {}", doubled.head());
    let sum = ne.fold(0, |acc, x| acc + x);
    println!("sum = {}", sum);

    assert!(NonEmptyVec::<i32>::from_vec(vec![]).is_none());

    // Approach 3: Const generic
    let sl = static_list([10, 20, 30]);
    println!("static head = {}, len = {}", sl.head(), sl.len());

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

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

    #[test]
    fn test_safe_list_head() {
        let list = SafeList::<_, Empty>::new().push(42);
        assert_eq!(*list.head(), 42);
    }

    #[test]
    fn test_safe_list_chain() {
        let list = SafeList::<_, Empty>::new().push(1).push(2).push(3);
        assert_eq!(*list.head(), 1);
        assert_eq!(list.tail(), &[2, 3]);
    }

    #[test]
    fn test_from_vec() {
        assert!(from_vec::<i32>(vec![]).is_none());
        let l = from_vec(vec![1, 2]).unwrap();
        assert_eq!(*l.head(), 1);
    }

    #[test]
    fn test_nonempty_vec() {
        let ne = NonEmptyVec::new(1, vec![2, 3]);
        assert_eq!(*ne.head(), 1);
        assert_eq!(ne.tail(), &[2, 3]);
    }

    #[test]
    fn test_nonempty_map() {
        let ne = NonEmptyVec::new(1, vec![2, 3]);
        let d = ne.map(|x| x * 2);
        assert_eq!(*d.head(), 2);
        assert_eq!(d.tail, vec![4, 6]);
    }

    #[test]
    fn test_nonempty_fold() {
        let ne = NonEmptyVec::new(1, vec![2, 3]);
        assert_eq!(ne.fold(0, |a, x| a + x), 6);
    }

    #[test]
    fn test_nonempty_from_vec() {
        assert!(NonEmptyVec::<i32>::from_vec(vec![]).is_none());
        let ne = NonEmptyVec::from_vec(vec![42]).unwrap();
        assert_eq!(*ne.head(), 42);
    }

    #[test]
    fn test_static_list() {
        let sl = static_list([10, 20, 30]);
        assert_eq!(*sl.head(), 10);
        assert_eq!(sl.len(), 3);
    }
}

(* Example 179: GADT Preventing Runtime Errors — Safe Head *)
(* A list type where head is guaranteed safe at compile time *)

(* Approach 1: Non-empty list GADT *)
type empty = Empty_tag
type nonempty = Nonempty_tag

type ('a, _) safe_list =
  | SNil  : ('a, empty) safe_list
  | SCons : 'a * ('a, _) safe_list -> ('a, nonempty) safe_list

let safe_head : type a. (a, nonempty) safe_list -> a = function
  | SCons (x, _) -> x

let safe_tail_list : type a s. (a, nonempty) safe_list -> a list = function
  | SCons (_, rest) ->
    let rec to_list : type s. (a, s) safe_list -> a list = function
      | SNil -> []
      | SCons (x, xs) -> x :: to_list xs
    in to_list rest

(* Approach 2: NonEmpty module *)
module NonEmpty = struct
  type 'a t = { head : 'a; tail : 'a list }

  let create head tail = { head; tail }
  let head ne = ne.head
  let tail ne = ne.tail
  let to_list ne = ne.head :: ne.tail
  let of_list = function
    | [] -> None
    | x :: xs -> Some { head = x; tail = xs }

  let map f ne = { head = f ne.head; tail = List.map f ne.tail }
  let fold_left f init ne = List.fold_left f (f init ne.head) ne.tail
end

(* Approach 3: Indexed by a boolean *)
type _ is_empty = Yes : empty is_empty | No : nonempty is_empty

type ('a, 's) ilist =
  | INil  : ('a, empty) ilist
  | ICons : 'a * ('a, _) ilist -> ('a, nonempty) ilist

let ihead : type a. (a, nonempty) ilist -> a = function
  | ICons (x, _) -> x

let () =
  (* Test Approach 1 *)
  let l = SCons (1, SCons (2, SCons (3, SNil))) in
  assert (safe_head l = 1);
  assert (safe_tail_list l = [2; 3]);

  (* This would not compile:
     let _ = safe_head SNil
  *)

  (* Test Approach 2 *)
  let ne = NonEmpty.create 1 [2; 3] in
  assert (NonEmpty.head ne = 1);
  assert (NonEmpty.tail ne = [2; 3]);
  assert (NonEmpty.to_list ne = [1; 2; 3]);
  let doubled = NonEmpty.map (fun x -> x * 2) ne in
  assert (NonEmpty.head doubled = 2);
  assert (NonEmpty.of_list [] = None);
  assert (NonEmpty.of_list [42] = Some { head = 42; tail = [] });
  let sum = NonEmpty.fold_left (+) 0 ne in
  assert (sum = 6);

  (* Test Approach 3 *)
  let il = ICons (10, ICons (20, INil)) in
  assert (ihead il = 10);

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 179 — Safe Head

Non-Empty List Type

OCaml

🐪 Show OCaml equivalent

type ('a, _) safe_list =
| SNil  : ('a, empty) safe_list
| SCons : 'a * ('a, _) safe_list -> ('a, nonempty) safe_list

let safe_head : type a. (a, nonempty) safe_list -> a = function
| SCons (x, _) -> x

Rust

struct SafeList<T, S> { data: Vec<T>, _state: PhantomData<S> }

impl<T> SafeList<T, NonEmpty> {
 fn head(&self) -> &T { &self.data[0] }
}
// SafeList<T, Empty> has NO head method — compile error if you try

NonEmpty Module/Struct

OCaml

🐪 Show OCaml equivalent

module NonEmpty = struct
type 'a t = { head : 'a; tail : 'a list }
let head ne = ne.head
let of_list = function [] -> None | x :: xs -> Some { head = x; tail = xs }
let map f ne = { head = f ne.head; tail = List.map f ne.tail }
end

Rust

struct NonEmptyVec<T> { head: T, tail: Vec<T> }

impl<T> NonEmptyVec<T> {
 fn head(&self) -> &T { &self.head }
 fn from_vec(v: Vec<T>) -> Option<Self> {
     let mut iter = v.into_iter();
     iter.next().map(|head| NonEmptyVec { head, tail: iter.collect() })
 }
 fn map<U>(&self, f: impl Fn(&T) -> U) -> NonEmptyVec<U> {
     NonEmptyVec { head: f(&self.head), tail: self.tail.iter().map(f).collect() }
 }
}

Type-State Transition

OCaml

🐪 Show OCaml equivalent

(* Constructing always gives nonempty *)
let l = SCons (1, SCons (2, SNil))  (* type: (int, nonempty) safe_list *)

Rust

let list = SafeList::<_, Empty>::new()  // Empty
 .push(1)                             // → NonEmpty
 .push(2);                            // still NonEmpty
// Type changes from SafeList<i32, Empty> to SafeList<i32, NonEmpty>

179: GADT Preventing Runtime Errors

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 179 — Safe Head

Non-Empty List Type

OCaml

Rust

NonEmpty Module/Struct

OCaml

Rust

Type-State Transition

OCaml

Rust

Related Examples