137 Expert

Rank-2 Types Simulation

Functional Programming

Tutorial

The Problem

A rank-2 type is a function that takes a polymorphic argument — a function that must work for all types, not just one specific type chosen by the caller. The classic example: runST :: (forall s. ST s a) -> a in Haskell prevents mutable state from leaking out of a computation. In Rust and OCaml, rank-2 polymorphism is simulated using traits with generic methods, which enforce "the callee chooses the type" rather than "the caller chooses the type."

🎯 Learning Outcomes

• Understand the difference between rank-1 (caller chooses type) and rank-2 (callee applies to all types) polymorphism

• Learn how Rust traits with generic methods simulate rank-2 types

• Understand why traits with generic methods are not dyn-compatible in Rust

• See practical applications: ST monad, generic fold callbacks, universally quantified data

Code Example

pub trait IdFn {
    fn apply<T>(&self, x: T) -> T;
}

pub struct Identity;

impl IdFn for Identity {
    fn apply<T>(&self, x: T) -> T { x }
}

// F: IdFn — NOT &dyn IdFn. Traits with generic methods are not dyn-compatible.
pub fn apply_id<F: IdFn>(f: &F) -> (i32, String) {
    let x = f.apply(42_i32);
    let y = f.apply("hello".to_string());
    (x, y)
}

(* Wrap the polymorphic function in a record to get rank-2 *)
type id_fn = { id : 'a. 'a -> 'a }

let apply_id (f : id_fn) =
  let x = f.id 42 in        (* int *)
  let y = f.id "hello" in   (* string *)
  (x, y)

let () =
  let result = apply_id { id = fun x -> x } in
  assert (result = (42, "hello"))

Key Differences

Native support: OCaml has native rank-2 types via record polymorphism ('a.); Rust simulates them with trait-based static dispatch.

Dyn compatibility: OCaml's rank-2 records can be stored in lists naturally; Rust's rank-2 traits cannot be used with dyn (generic methods prevent it).

Ergonomics: OCaml's { apply = fun x -> x } is compact; Rust requires defining a struct and an impl IdFn block.

Type inference: OCaml infers rank-2 types in most cases; Rust requires explicit trait bounds everywhere rank-2 behavior is needed.

OCaml Approach

OCaml supports rank-2 types natively via record polymorphism:

type id_fn = { apply : 'a. 'a -> 'a }
let apply_id f = (f.apply 42, f.apply "hello")
let identity = { apply = fun x -> x }

The 'a. prefix in the record field type means "for all 'a". This is more ergonomic than Rust's trait simulation and supports dyn-style usage naturally. OCaml's runST equivalent is straightforward with this mechanism.

Full Source

#![allow(clippy::all)]
//! # Rank-2 Types Simulation in Rust
//!
//! Rust lacks native rank-2 polymorphism, but traits with generic methods
//! serve as an equivalent: a trait bound forces the caller to supply something
//! that works for *every* type the trait method is called with.
//!
//! Crucially, traits with generic methods are **not** dyn-compatible in Rust
//! (they can't be used with `dyn Trait`). Rank-2 is therefore encoded via
//! *static dispatch* — `F: IdFn` — not dynamic dispatch. This is actually
//! the more faithful analogue to OCaml's record-polymorphism and first-class
//! modules.

// ---------------------------------------------------------------------------
// Approach 1: Trait-based rank-2 identity
// ---------------------------------------------------------------------------
// `trait IdFn` is the "for all T" contract. Any implementor must handle every T.
// `apply_id` can therefore call `f.apply` with an i32 *and* a String in one go.
// The caller cannot specialize `apply` to a single type — the callee owns that.

pub trait IdFn {
    fn apply<T>(&self, x: T) -> T;
}

pub struct Identity;

impl IdFn for Identity {
    fn apply<T>(&self, x: T) -> T {
        x
    }
}

/// Apply a rank-2 identity function to two different types in a single call.
/// Note: `F: IdFn` (static dispatch) — not `dyn IdFn`, which is not allowed
/// because generic methods are not dyn-compatible.
pub fn apply_id<F: IdFn>(f: &F) -> (i32, String) {
    let x = f.apply(42_i32);
    let y = f.apply("hello".to_string());
    (x, y)
}

// ---------------------------------------------------------------------------
// Approach 2: Rank-2 "for-all" callback with Debug bound
// ---------------------------------------------------------------------------
// The trait carries a generic method, so the implementor must work for any
// `T: fmt::Debug`. This lets `apply_forall` call it with heterogeneous types.

pub trait ForAll {
    fn call<T: std::fmt::Debug>(&self, val: T) -> String;
}

pub struct ShowDebug;

impl ForAll for ShowDebug {
    fn call<T: std::fmt::Debug>(&self, val: T) -> String {
        format!("{val:?}")
    }
}

/// Apply a rank-2 "format as debug" function to multiple distinct types.
pub fn apply_forall<F: ForAll>(f: &F) -> Vec<String> {
    vec![f.call(42_i32), f.call("world"), f.call(vec![1_u8, 2, 3])]
}

// ---------------------------------------------------------------------------
// Approach 3: Rank-2 via higher-ranked trait bounds (HRTBs)
// ---------------------------------------------------------------------------
// Rust's `for<'a>` syntax is the closest native form of rank-2: a closure
// that must be valid for *every* lifetime, not just one chosen by the caller.
// This is rank-2 over lifetimes. We use it to apply a function to references
// of different-scoped data within a single call.

/// Accept any function that works for *any* lifetime `'a`, apply it to two
/// independently-scoped references, and return both results.
pub fn apply_twice_hrtb<F>(f: F) -> (usize, usize)
where
    F: for<'a> Fn(&'a str) -> usize,
{
    let result1 = {
        let s1 = String::from("hello world");
        f(&s1)
    };
    let result2 = {
        let s2 = String::from("rank-2");
        f(&s2)
    };
    (result1, result2)
}

// ---------------------------------------------------------------------------
// Approach 4: ST-monad style — rank-2 prevents state from leaking
// ---------------------------------------------------------------------------
// In Haskell/OCaml the phantom type `s` is existentially quantified at the
// boundary so no `STRef s a` can escape `runST`. In Rust we encode the same
// discipline with a lifetime brand: `s` is an invariant lifetime that the
// closure must be generic over, which the compiler enforces.
//
// The simplified version: a trait that represents a "pure state action"
// whose result type is fixed, so no internal state references can leak.

pub trait StAction {
    /// Run the state action and return a result that does not carry `s`.
    fn run(&self) -> i32;
}

pub struct CountRef {
    pub initial: i32,
}

impl StAction for CountRef {
    fn run(&self) -> i32 {
        // Simulate: new_ref(initial), increment, read — result escapes, ref doesn't.
        let mut val = self.initial;
        val += 1;
        val
    }
}

/// Accept any `StAction` — the result type is fixed (i32), so no internal
/// state can "leak" through the return type.
pub fn run_st<A: StAction>(action: &A) -> i32 {
    action.run()
}

// ---------------------------------------------------------------------------
// Approach 5: Apply a polymorphic transformation to a heterogeneous pair
// ---------------------------------------------------------------------------

pub struct HetPair<A, B>(pub A, pub B);

pub trait MapPair<A, B> {
    fn map_pair(&self, pair: HetPair<A, B>) -> HetPair<A, B>;
}

pub struct ClonePair;

impl<A: Clone, B: Clone> MapPair<A, B> for ClonePair {
    fn map_pair(&self, pair: HetPair<A, B>) -> HetPair<A, B> {
        HetPair(pair.0.clone(), pair.1.clone())
    }
}

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

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

    #[test]
    fn test_identity_applies_to_two_types() {
        let id = Identity;
        let (n, s) = apply_id(&id);
        assert_eq!(n, 42);
        assert_eq!(s, "hello");
    }

    #[test]
    fn test_identity_preserves_value_for_multiple_types() {
        let id = Identity;
        assert_eq!(id.apply(99_u64), 99_u64);
        assert_eq!(id.apply("rust"), "rust");
        assert_eq!(id.apply(3.14_f64), 3.14_f64);
    }

    #[test]
    fn test_forall_formats_different_types() {
        let show = ShowDebug;
        let results = apply_forall(&show);
        assert_eq!(results[0], "42");
        assert_eq!(results[1], "\"world\"");
        assert_eq!(results[2], "[1, 2, 3]");
    }

    #[test]
    fn test_forall_call_directly() {
        let show = ShowDebug;
        assert_eq!(show.call(true), "true");
        assert_eq!(show.call(0_i32), "0");
    }

    #[test]
    fn test_hrtb_applies_to_different_scopes() {
        let (a, b) = apply_twice_hrtb(|s| s.len());
        assert_eq!(a, 11); // "hello world"
        assert_eq!(b, 6); // "rank-2"
    }

    #[test]
    fn test_hrtb_with_word_count() {
        let count_words = |s: &str| s.split_whitespace().count();
        let (a, b) = apply_twice_hrtb(count_words);
        assert_eq!(a, 2); // "hello world" → 2 words
        assert_eq!(b, 1); // "rank-2" → 1 word
    }

    #[test]
    fn test_st_action_result_escapes_state_does_not() {
        let action = CountRef { initial: 5 };
        assert_eq!(run_st(&action), 6);
    }

    #[test]
    fn test_st_action_pure_runs_consistently() {
        let action = CountRef { initial: 10 };
        // Running twice should return the same pure result each time.
        assert_eq!(run_st(&action), run_st(&action));
    }

    #[test]
    fn test_het_pair_clone() {
        let mapper = ClonePair;
        let pair = HetPair(42_i32, "hello".to_string());
        let result = mapper.map_pair(pair);
        assert_eq!(result.0, 42);
        assert_eq!(result.1, "hello");
    }
}

(* Example 137: Rank-2 Types *)
(* A rank-2 function takes a polymorphic function as argument *)

(* Approach 1: Using records to encode rank-2 polymorphism *)
type id_fn = { id : 'a. 'a -> 'a }

let apply_id (f : id_fn) =
  let x = f.id 42 in
  let y = f.id "hello" in
  (x, y)

(* Approach 2: Rank-2 with first-class modules *)
module type TRANSFORM = sig
  val transform : 'a -> 'a
end

let apply_transform (module T : TRANSFORM) =
  (T.transform 42, T.transform "hello")

module Identity : TRANSFORM = struct
  let transform x = x
end

(* Approach 3: ST monad simulation — rank-2 prevents leaking *)
type ('s, 'a) st_ref = { mutable st_contents : 'a }

type 'a st_action = { run : 's. unit -> 'a }

let new_ref v = { st_contents = v }
let read_ref r = r.st_contents
let write_ref r v = r.st_contents <- v

let run_st (action : 'a st_action) : 'a = action.run ()

(* Tests *)
let () =
  let result = apply_id { id = fun x -> x } in
  assert (fst result = 42);
  assert (snd result = "hello");

  let (i, s) = apply_transform (module Identity) in
  assert (i = 42);
  assert (s = "hello");

  let result = run_st { run = fun () ->
    let r = new_ref 0 in
    write_ref r 42;
    read_ref r
  } in
  assert (result = 42);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_identity_applies_to_two_types() {
        let id = Identity;
        let (n, s) = apply_id(&id);
        assert_eq!(n, 42);
        assert_eq!(s, "hello");
    }

    #[test]
    fn test_identity_preserves_value_for_multiple_types() {
        let id = Identity;
        assert_eq!(id.apply(99_u64), 99_u64);
        assert_eq!(id.apply("rust"), "rust");
        assert_eq!(id.apply(3.14_f64), 3.14_f64);
    }

    #[test]
    fn test_forall_formats_different_types() {
        let show = ShowDebug;
        let results = apply_forall(&show);
        assert_eq!(results[0], "42");
        assert_eq!(results[1], "\"world\"");
        assert_eq!(results[2], "[1, 2, 3]");
    }

    #[test]
    fn test_forall_call_directly() {
        let show = ShowDebug;
        assert_eq!(show.call(true), "true");
        assert_eq!(show.call(0_i32), "0");
    }

    #[test]
    fn test_hrtb_applies_to_different_scopes() {
        let (a, b) = apply_twice_hrtb(|s| s.len());
        assert_eq!(a, 11); // "hello world"
        assert_eq!(b, 6); // "rank-2"
    }

    #[test]
    fn test_hrtb_with_word_count() {
        let count_words = |s: &str| s.split_whitespace().count();
        let (a, b) = apply_twice_hrtb(count_words);
        assert_eq!(a, 2); // "hello world" → 2 words
        assert_eq!(b, 1); // "rank-2" → 1 word
    }

    #[test]
    fn test_st_action_result_escapes_state_does_not() {
        let action = CountRef { initial: 5 };
        assert_eq!(run_st(&action), 6);
    }

    #[test]
    fn test_st_action_pure_runs_consistently() {
        let action = CountRef { initial: 10 };
        // Running twice should return the same pure result each time.
        assert_eq!(run_st(&action), run_st(&action));
    }

    #[test]
    fn test_het_pair_clone() {
        let mapper = ClonePair;
        let pair = HetPair(42_i32, "hello".to_string());
        let result = mapper.map_pair(pair);
        assert_eq!(result.0, 42);
        assert_eq!(result.1, "hello");
    }
}

Deep Comparison

OCaml vs Rust: Rank-2 Types

The Core Problem

Rank-2 polymorphism lets you pass a function that must work for any type — not a single type chosen by the caller. In rank-1 (normal) generics, the caller picks the type parameter. In rank-2, the callee picks it (potentially multiple times, with different types in sequence).

Side-by-Side Code

OCaml — record-encoded rank-2

(* Wrap the polymorphic function in a record to get rank-2 *)
type id_fn = { id : 'a. 'a -> 'a }

let apply_id (f : id_fn) =
  let x = f.id 42 in        (* int *)
  let y = f.id "hello" in   (* string *)
  (x, y)

let () =
  let result = apply_id { id = fun x -> x } in
  assert (result = (42, "hello"))

OCaml — first-class module rank-2

module type TRANSFORM = sig
  val transform : 'a -> 'a
end

let apply_transform (module T : TRANSFORM) =
  (T.transform 42, T.transform "hello")

module Identity : TRANSFORM = struct
  let transform x = x
end

let () =
  let (n, s) = apply_transform (module Identity) in
  assert (n = 42 && s = "hello")

Rust — trait with generic method (rank-2 via static dispatch)

pub trait IdFn {
    fn apply<T>(&self, x: T) -> T;
}

pub struct Identity;

impl IdFn for Identity {
    fn apply<T>(&self, x: T) -> T { x }
}

// F: IdFn — NOT &dyn IdFn. Traits with generic methods are not dyn-compatible.
pub fn apply_id<F: IdFn>(f: &F) -> (i32, String) {
    let x = f.apply(42_i32);
    let y = f.apply("hello".to_string());
    (x, y)
}

Rust — ForAll trait with Debug bound

pub trait ForAll {
    fn call<T: std::fmt::Debug>(&self, val: T) -> String;
}

pub struct ShowDebug;

impl ForAll for ShowDebug {
    fn call<T: std::fmt::Debug>(&self, val: T) -> String {
        format!("{val:?}")
    }
}

pub fn apply_forall<F: ForAll>(f: &F) -> Vec<String> {
    vec![f.call(42_i32), f.call("world"), f.call(vec![1_u8, 2, 3])]
}

Rust — rank-2 over lifetimes (Higher-Ranked Trait Bounds)

// `for<'a>` is Rust's native rank-2: must work for every lifetime, not one chosen by caller.
pub fn apply_twice_hrtb<F>(f: F) -> (usize, usize)
where
    F: for<'a> Fn(&'a str) -> usize,
{
    let result1 = { let s1 = String::from("hello world"); f(&s1) };
    let result2 = { let s2 = String::from("rank-2"); f(&s2) };
    (result1, result2)
}

Type Signatures

Concept	OCaml	Rust
Rank-2 type	`{ id : 'a. 'a -> 'a }`	`trait IdFn { fn apply<T>(&self, x: T) -> T; }`
Universal quantifier	`'a.` (explicit in record)	Implicit in trait's generic method parameter
Encoding mechanism	Record field / first-class module	Trait bound `F: IdFn` (static dispatch)
Dispatch style	Structural (record field, module)	Monomorphisation (zero-cost)
Native rank-2 syntax	`'a.` in record type	`for<'a>` in HRTB (lifetime level only)

Key Insights

*Rust traits with generic methods are not dyn-compatible.*

Unlike OCaml records, you cannot erase a trait with generic methods into &dyn Trait — the compiler cannot build a vtable for a method whose concrete type isn't known. Rank-2 in Rust is therefore encoded via static dispatch (F: IdFn), not dynamic dispatch. This is actually more performant: zero overhead, monomorphised at compile time.

OCaml uses records; Rust uses trait bounds.

OCaml annotates a record field with 'a. (an explicit universal quantifier), forcing any record value to carry a function that works for all 'a. Rust's equivalent is F: IdFn where IdFn has a generic method — the compiler enforces that F must handle every T the method might be called with.

**for<'a> is Rust's native rank-2 — but only over lifetimes.**

Rust's higher-ranked trait bounds (for<'a> Fn(&'a str) -> usize) are genuine rank-2: the caller cannot fix 'a; the callee uses the function with independently-scoped borrows. This mirrors Haskell's runST pattern and is the language's built-in rank-2 mechanism — though only over lifetimes, not types.

First-class modules ↔ generic type parameters.

OCaml's (module T : TRANSFORM) passes a module whose transform is universally polymorphic. Rust's <F: ForAll>(f: &F) is structurally identical: F must implement call<T> for all T, and the concrete type is resolved at compile time by the monomorphiser.

ST-monad safety: rank-2 as an escape hatch.

In Haskell's runST and OCaml's ST simulation, rank-2 prevents mutable state references from leaking out of a computation. Rust achieves the same with lifetime branding (an invariant phantom lifetime 's): the type system statically rejects any attempt to let a &'s mut T escape the closure that created it, without needing rank-2 over types at all.

When to Use Each Style

**Use F: IdFn (generic bound / static dispatch)** when the concrete implementor is always known at compile time and you want zero-cost monomorphisation — equivalent to OCaml's first-class modules resolved by the compiler.

**Use for<'a> HRTBs** when you need a closure or function that must be valid for every possible lifetime — the canonical Rust use case is fn(&T) -> U callbacks in APIs that hold borrows of varying lifetimes.

Use the ST-lifetime-brand pattern when you need to guarantee that mutable state created inside a scope cannot escape it — a safety property that rank-2 enforces at the type level in both OCaml and Rust.

Exercises

Implement a PolyMapper trait with fn map<T, U>(&self, f: impl Fn(T) -> U, x: T) -> U and use it to apply transformations to different types in one call.

Write apply_to_pair<F: IdFn>(f: &F, x: i32, y: String) -> (i32, String) using the same F for both.

Implement a RunST-like pattern where a computation over a phantom state type S prevents values from escaping their scope.

Open Source Repos

functional-rust

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

Rust