179 Expert

GADT Preventing Runtime Errors — Safe Head

Functional Programming

Tutorial

The Problem

head on an empty list is undefined. Instead of returning Option<T> and forcing callers to handle None, the typestate approach encodes emptiness in the type: SafeList<T, NonEmpty> has a head method; SafeList<T, Empty> does not. This converts a potential runtime panic into a compile error, and callers never need to unwrap. The pattern generalizes to any operation that requires a precondition: safe division, safe array access, safe database reads.

🎯 Learning Outcomes

• Encode list emptiness as a phantom type state (Empty vs. NonEmpty)

• Implement head only on SafeList<T, NonEmpty> — calling it on an empty list is a compile error

• See how push transitions from SafeList<T, Empty> to SafeList<T, NonEmpty>

• Understand this as a specialized typestate pattern (example 130) applied to data structures

Code Example

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

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

Key Differences

Exhaustiveness: OCaml's GADT head on nonempty lists has no Nil case — it's impossible; Rust's impl SafeList<T, NonEmpty> block achieves the same by not defining the method on Empty.

Transition type: OCaml's Cons constructor changes the type index directly; Rust's push consumes the old value and returns a new type.

Runtime cost: Both are zero-cost — PhantomData/phantom types vanish at runtime.

Practical use: Rust's typestate is used in the rusqlite crate (transaction states), tokio (task states), and custom protocol implementations.

OCaml Approach

OCaml's GADT approach is more elegant:

type empty = Empty
type nonempty = Nonempty
type ('a, 's) safe_list =
  | Nil  : ('a, empty) safe_list
  | Cons : 'a * ('a, _) safe_list -> ('a, nonempty) safe_list
let head : ('a, nonempty) safe_list -> 'a = function Cons (x, _) -> x

Pattern matching on Nil in head is rejected by the compiler — OCaml's GADT exhaustiveness checker knows nonempty lists are never Nil.

Full Source

#![allow(clippy::all)]
// 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 }
}

#[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"

✓ Tests Rust test suite

#[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);
    }
}

Deep Comparison

Comparison: Example 179 — Safe Head

Non-Empty List Type

OCaml

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

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

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

Exercises

Add a tail(self) -> (T, SafeList<T, ...>) method that returns a SafeList<T, NonEmpty> if the original had 2+ elements, or SafeList<T, Empty> if exactly 1.

Implement first_two(&self) -> (&T, &T) only on lists with at least two elements — requiring a TwoOrMore phantom state.

Implement a safe_dequeue for a SafeQueue type with Enqueue and Dequeue operations that prevent dequeuing from an empty queue.

Open Source Repos

functional-rust

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

Rust