139: HList — Heterogeneous List

Difficulty: ⭐⭐⭐ Level: Advanced A type-safe list of mixed types where the full type of each element is preserved and accessible at compile time — unlike tuples (fixed structure), `Vec` (uniform type), or `Box<dyn Any>` (runtime type).

The Problem This Solves

Tuples in Rust hold mixed types — `(i32, &str, f64)` — but they're structurally fixed. You can't write generic code that "iterates" a tuple, appends to it, or extracts the nth element when n is a runtime value. `Vec<T>` handles any length but requires all elements to be the same type. `Vec<Box<dyn Any>>` loses type information and requires unsafe downcasting. What if you need a collection that is both heterogeneous (different element types) and type-safe (types fully preserved and accessible without casts)? Serialization frameworks that process fields of different types, function composition chains where each step changes the type, database row types — all of these need something that tuples can't express generically and Vec can't express at all. An HList (heterogeneous list) is the answer. `HCons<i32, HCons<&str, HCons<f64, HNil>>>` is a type that carries exactly three elements of exactly those types. `head()` returns `&i32`. `tail().head()` returns `&&str`. The full type information is preserved, and you can write generic code over any HList using recursive trait impls.

The Intuition

An HList is built from two constructors — just like a regular linked list, but in the type system:

`HNil` — the empty list
`HCons<H, T>` — an element `H` prepended to tail `T`

So `hlist!(42, "hello", true)` has type `HCons<i32, HCons<&str, HCons<bool, HNil>>>`. Every element's type is part of the overall type. The length is also encoded: `HNil` has length 0, `HCons<_, T>` has length 1 + len(T) — computable at compile time. You access elements by traversing the type structure: `.head()` gives the first element, `.tail()` drops it, `.tail().head()` gives the second, and so on. The compiler tracks the type at each position — no casts.

How It Works in Rust

// Two constructors — the entire HList type system
struct HNil;                    // empty list
struct HCons<H, T>(H, T);      // head :: tail

// Compute length at compile time via recursive trait
trait HLength { const LEN: usize; }
impl HLength for HNil { const LEN: usize = 0; }
impl<H, T: HLength> HLength for HCons<H, T> {
 const LEN: usize = 1 + T::LEN;  // recursion in the type system
}

// Access head — only on non-empty lists
trait Head {
 type Output;
 fn head(&self) -> &Self::Output;
}
impl<H, T> Head for HCons<H, T> {
 type Output = H;
 fn head(&self) -> &H { &self.0 }
}

// Access tail — only on non-empty lists
trait Tail {
 type Output;
 fn tail(&self) -> &Self::Output;
}
impl<H, T> Tail for HCons<H, T> {
 type Output = T;
 fn tail(&self) -> &T { &self.1 }
}

// Ergonomic construction macro
macro_rules! hlist {
 () => { HNil };
 ($head:expr $(, $tail:expr)*) => { HCons($head, hlist!($($tail),*)) }
}

// Type alias macro for cleaner signatures
macro_rules! hlist_type {
 () => { HNil };
 ($head:ty $(, $tail:ty)*) => { HCons<$head, hlist_type!($($tail),*)> }
}

// Debug-style display via recursive trait
trait HDisplay { fn h_display(&self) -> String; }
impl HDisplay for HNil { fn h_display(&self) -> String { String::new() } }
impl<H: std::fmt::Debug, T: HDisplay> HDisplay for HCons<H, T> {
 fn h_display(&self) -> String {
     let rest = self.1.h_display();
     if rest.is_empty() { format!("{:?}", self.0) }
     else { format!("{:?}, {}", self.0, rest) }
 }
}

Usage:

let list = hlist!(42, "hello", 3.14, true);

// Each access is type-safe — compiler knows the type at each position
let first: &i32  = list.head();           // 42
let second: &&str = list.tail().head();    // "hello"
let third: &f64  = list.tail().tail().head();  // 3.14

// Length is a compile-time constant
let len = <hlist_type!(i32, &str, f64, bool) as HLength>::LEN;  // 4

// Typed declarations
let typed: hlist_type!(i32, &str) = hlist!(1, "two");
println!("{}", typed.h_display());  // "1, \"two\""

What This Unlocks

Typed record composition — build function pipelines where each step adds a field to a typed record, with no HashMap and no dynamic dispatch.
Frunk / generic programming — the `frunk` crate uses HList as the foundation for generic derive, type-safe lenses, and structural subtyping.
Variadic functions — simulate functions with variable argument counts where each argument's type is tracked; useful for test frameworks, SQL query builders, and RPC frameworks.

Key Differences

Concept	OCaml	Rust
HList type	GADT: `type _ hlist = HNil : hnil hlist \	HCons : 'a * 'b hlist -> ('a,'b) hcons hlist`	Structs: `struct HNil; struct HCons<H, T>(H, T)`
Element access	Pattern match: `let HCons (x, _) = h`	Trait methods: `h.head()`, `h.tail()`
Generic algorithms	Type-level recursion via GADT	Recursive trait impls: one for `HNil`, one for `HCons<H, T>`
Construction	Explicit `HCons (42, HCons ("hello", HNil))`	`hlist!(42, "hello")` macro

// Example 139: HList — Heterogeneous List
// Type-safe list of mixed types using recursive tuple types

// Approach 1: HList via nested tuples
struct HNil;
struct HCons<H, T>(H, T);

// Type-safe constructors
fn hnil() -> HNil { HNil }
fn hcons<H, T>(head: H, tail: T) -> HCons<H, T> { HCons(head, tail) }

// Length trait
trait HLength {
    const LEN: usize;
}

impl HLength for HNil {
    const LEN: usize = 0;
}

impl<H, T: HLength> HLength for HCons<H, T> {
    const LEN: usize = 1 + T::LEN;
}

// Head and Tail accessors
trait Head {
    type Output;
    fn head(&self) -> &Self::Output;
}

impl<H, T> Head for HCons<H, T> {
    type Output = H;
    fn head(&self) -> &H { &self.0 }
}

trait Tail {
    type Output;
    fn tail(&self) -> &Self::Output;
}

impl<H, T> Tail for HCons<H, T> {
    type Output = T;
    fn tail(&self) -> &T { &self.1 }
}

// Approach 2: HList with map/fold via trait
trait HMap<F> {
    type Output;
    fn hmap(self, f: &F) -> Self::Output;
}

impl<F> HMap<F> for HNil {
    type Output = HNil;
    fn hmap(self, _: &F) -> HNil { HNil }
}

// Approach 3: Macro for ergonomic HList construction
macro_rules! hlist {
    () => { HNil };
    ($head:expr $(, $tail:expr)*) => {
        HCons($head, hlist!($($tail),*))
    };
}

macro_rules! hlist_type {
    () => { HNil };
    ($head:ty $(, $tail:ty)*) => {
        HCons<$head, hlist_type!($($tail),*)>
    };
}

// Approach 3b: Display for HList
trait HDisplay {
    fn h_display(&self) -> String;
}

impl HDisplay for HNil {
    fn h_display(&self) -> String { String::new() }
}

impl<H: std::fmt::Debug, T: HDisplay> HDisplay for HCons<H, T> {
    fn h_display(&self) -> String {
        let rest = self.1.h_display();
        if rest.is_empty() {
            format!("{:?}", self.0)
        } else {
            format!("{:?}, {}", self.0, rest)
        }
    }
}

fn main() {
    // Build HList
    let list = hlist!(42, "hello", 3.14, true);
    println!("Head: {:?}", list.head());
    println!("Second: {:?}", list.tail().head());
    println!("Third: {:?}", list.tail().tail().head());
    println!("Length: {}", <HCons<i32, HCons<&str, HCons<f64, HCons<bool, HNil>>>> as HLength>::LEN);
    println!("Display: [{}]", list.h_display());

    // Type is fully known at compile time
    let typed: hlist_type!(i32, &str, f64) = hlist!(1, "two", 3.0);
    println!("Typed: [{}]", typed.h_display());
}

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

    #[test]
    fn test_hlist_construction() {
        let list = hlist!(42, "hello", true);
        assert_eq!(*list.head(), 42);
        assert_eq!(*list.tail().head(), "hello");
        assert_eq!(*list.tail().tail().head(), true);
    }

    #[test]
    fn test_hlist_length() {
        assert_eq!(<HNil as HLength>::LEN, 0);
        assert_eq!(<HCons<i32, HNil> as HLength>::LEN, 1);
        assert_eq!(<HCons<i32, HCons<&str, HNil>> as HLength>::LEN, 2);
    }

    #[test]
    fn test_hlist_display() {
        let list = hlist!(42, "hello");
        assert_eq!(list.h_display(), "42, \"hello\"");
    }

    #[test]
    fn test_empty_hlist() {
        let empty = hlist!();
        assert_eq!(<HNil as HLength>::LEN, 0);
        assert_eq!(empty.h_display(), "");
    }

    #[test]
    fn test_single_element() {
        let single = hlist!(42);
        assert_eq!(*single.head(), 42);
        assert_eq!(single.h_display(), "42");
    }
}

(* Example 139: HList — Heterogeneous List *)

(* Approach 1: GADT heterogeneous list *)
type hnil = HNil_t
type ('h, 't) hcons = HCons_t

type _ hlist =
  | HNil : hnil hlist
  | HCons : 'a * 'b hlist -> ('a, 'b) hcons hlist

let empty = HNil
let ex1 = HCons (42, HCons ("hello", HCons (true, HNil)))

let hd : type a b. (a, b) hcons hlist -> a = function
  | HCons (x, _) -> x

let tl : type a b. (a, b) hcons hlist -> b hlist = function
  | HCons (_, rest) -> rest

(* Approach 2: Existential list (loses type info) *)
type any = Any : 'a -> any

let any_list = [Any 42; Any "hello"; Any true]

(* Approach 3: Tuple-based HList via nesting *)
type ('a, 'b) pair = { fst : 'a; snd : 'b }

let hlist3 a b c = { fst = a; snd = { fst = b; snd = c } }
let get_first p = p.fst
let get_second p = p.snd.fst
let get_third p = p.snd.snd

(* Tests *)
let () =
  let h = HCons (42, HCons ("hello", HCons (3.14, HNil))) in
  assert (hd h = 42);
  assert (hd (tl h) = "hello");
  assert (hd (tl (tl h)) = 3.14);

  let p = hlist3 1 "two" 3.0 in
  assert (get_first p = 1);
  assert (get_second p = "two");
  assert (get_third p = 3.0);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: HList

OCaml

🐪 Show OCaml equivalent

type _ hlist =
| HNil : hnil hlist
| HCons : 'a * 'b hlist -> ('a, 'b) hcons hlist

let h = HCons (42, HCons ("hello", HNil))
let x = hd h        (* 42 *)
let y = hd (tl h)   (* "hello" *)

Rust

struct HNil;
struct HCons<H, T>(H, T);

macro_rules! hlist {
 () => { HNil };
 ($h:expr $(, $t:expr)*) => { HCons($h, hlist!($($t),*)) };
}

let h = hlist!(42, "hello", true);
let x = h.head();           // &42
let y = h.tail().head();    // &"hello"