142 Expert

Type Equality

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Type Equality" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. In advanced generic programming, you sometimes need to express and prove that two type parameters are the same type. Key difference from OCaml: 1. **GADT convenience**: OCaml's `Refl : ('a, 'a) eq` directly encodes the equality; Rust must use workarounds since native GADTs are not available.

Tutorial

The Problem

In advanced generic programming, you sometimes need to express and prove that two type parameters are the same type. This arises in type-safe casts, in GADT-style encodings, and in generic code that needs to branch on whether two type parameters are equal. A type equality witness Eq<A, B> is a value that proves A = B at the type level, enabling safe casts without unsafe code and without dynamic type checking.

🎯 Learning Outcomes

• Understand what a type equality proof is and why it is useful

• Learn how to encode type equality witnesses in Rust using marker traits

• See how a TypeEq<A, B> value enables safe coercion between A and B

• Understand the connection to Leibniz equality and substitution in type theory

Code Example

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Type equality witnesses: a value of type ('a, 'b) eq proves a = b.
   Useful in GADTs to unify type variables. *)

(* Leibniz equality: a = b iff for all F, F a = F b *)
type ('a, 'b) eq = { cast : 'r. 'r 'a -> 'r 'b }

(* Or simpler with GADTs: *)
type (_, _) teq = Refl : ('a, 'a) teq

(* Using Refl to cast values *)
let cast_with : type a b. (a, b) teq -> a -> b = fun Refl x -> x

(* Symmetry: if a = b then b = a *)
let sym : type a b. (a, b) teq -> (b, a) teq = fun Refl -> Refl

(* Transitivity: if a = b and b = c then a = c *)
let trans : type a b c. (a, b) teq -> (b, c) teq -> (a, c) teq =
  fun Refl Refl -> Refl

let () =
  let eq_int : (int, int) teq = Refl in
  let n : int = 42 in
  let m : int = cast_with eq_int n in
  assert (n = m);
  Printf.printf "cast_with Refl: %d\n" m;

  (* Symmetry *)
  let _sym_eq : (int, int) teq = sym eq_int in
  Printf.printf "Type equality proofs work\n"

Key Differences

GADT convenience: OCaml's Refl : ('a, 'a) eq directly encodes the equality; Rust must use workarounds since native GADTs are not available.

Coercion: OCaml's cast using Refl requires no unsafe; Rust's type equality coercions sometimes require unsafe transmute unless carefully structured.

Runtime vs. compile time: Rust's TypeId-based equality is a runtime check; OCaml's GADT eq is purely compile-time.

Standard library: OCaml's eq type is definable in user code and used in Base/Core; Rust lacks a standard type equality witness, though crates provide them.

OCaml Approach

OCaml encodes type equality via GADTs:

type (_, _) eq = Refl : ('a, 'a) eq
let cast : type a b. (a, b) eq -> a -> b = fun Refl x -> x

Refl is only constructible for equal types, and pattern matching on Refl refines the type checker to know a = b in the match branch, enabling safe coercions. This is the standard technique in OCaml generic programming.

Full Source

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Type equality witnesses: a value of type ('a, 'b) eq proves a = b.
   Useful in GADTs to unify type variables. *)

(* Leibniz equality: a = b iff for all F, F a = F b *)
type ('a, 'b) eq = { cast : 'r. 'r 'a -> 'r 'b }

(* Or simpler with GADTs: *)
type (_, _) teq = Refl : ('a, 'a) teq

(* Using Refl to cast values *)
let cast_with : type a b. (a, b) teq -> a -> b = fun Refl x -> x

(* Symmetry: if a = b then b = a *)
let sym : type a b. (a, b) teq -> (b, a) teq = fun Refl -> Refl

(* Transitivity: if a = b and b = c then a = c *)
let trans : type a b c. (a, b) teq -> (b, c) teq -> (a, c) teq =
  fun Refl Refl -> Refl

let () =
  let eq_int : (int, int) teq = Refl in
  let n : int = 42 in
  let m : int = cast_with eq_int n in
  assert (n = m);
  Printf.printf "cast_with Refl: %d\n" m;

  (* Symmetry *)
  let _sym_eq : (int, int) teq = sym eq_int in
  Printf.printf "Type equality proofs work\n"

Deep Comparison

OCaml vs Rust: Type Equality

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement a same_type<A: 'static, B: 'static>() -> bool using TypeId for runtime type equality checking.

Design a TypeEq<A, B> marker trait with an unsafe fn coerce(a: A) -> B method, implemented only for TypeEq<T, T>.

Write a generic function that branches on type equality: fn stringify_if_str<T: 'static>(val: T) -> Option<String>.

Open Source Repos

functional-rust

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

Rust