144 Advanced

Generic Associated Types (GAT) Basics

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Generic Associated Types (GAT) Basics" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Before Generic Associated Types (GATs, stable in Rust 1.65), it was impossible to write a trait whose associated types were themselves generic over a lifetime or type parameter. Key difference from OCaml: 1. **Stability**: Rust GATs became stable in 1.65 (2022); OCaml's parameterized module types have been stable since OCaml 1.0.

Tutorial

The Problem

Before Generic Associated Types (GATs, stable in Rust 1.65), it was impossible to write a trait whose associated types were themselves generic over a lifetime or type parameter. This blocked implementing traits like LendingIterator (where each call to next borrows from the iterator itself) or a generic Container trait with a map method that changes the element type. GATs fill this gap, enabling patterns previously impossible in stable Rust.

🎯 Learning Outcomes

• Understand what Generic Associated Types are and the problems they solve

• Learn the GAT syntax: type Mapped<U> and type Iter<'a> inside trait definitions

• See how GATs enable lifetime-generic associated types (the lending iterator pattern)

• Understand the current limitations and workarounds in stable Rust's GAT support

Code Example

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

(* GADTs (Generalized Algebraic Data Types): each constructor can
   fix the type parameter differently. The type carries proof information. *)

(* Classic: typed expression tree *)
type _ expr =
  | Int  : int  -> int expr
  | Bool : bool -> bool expr
  | Add  : int expr * int expr -> int expr
  | If   : bool expr * 'a expr * 'a expr -> 'a expr
  | Eq   : int expr * int expr -> bool expr

(* Type-safe eval: the return type matches the GADT parameter *)
let rec eval : type a. a expr -> a = function
  | Int n          -> n
  | Bool b         -> b
  | Add (l, r)     -> eval l + eval r
  | If (c, t, e)   -> if eval c then eval t else eval e
  | Eq (l, r)      -> eval l = eval r

let () =
  let e1 = Add (Int 3, Int 4) in
  Printf.printf "3 + 4 = %d\n" (eval e1);

  let e2 = If (Bool true, Int 10, Int 20) in
  Printf.printf "if true then 10 else 20 = %d\n" (eval e2);

  let e3 = If (Eq (Int 1, Int 1), Bool true, Bool false) in
  Printf.printf "if 1=1 then true else false = %b\n" (eval e3);

  let e4 = If (Eq (Add (Int 2, Int 3), Int 5), Int 42, Int 0) in
  Printf.printf "if 2+3=5 then 42 else 0 = %d\n" (eval e4)

Key Differences

Stability: Rust GATs became stable in 1.65 (2022); OCaml's parameterized module types have been stable since OCaml 1.0.

Lifetime GATs: Rust GATs can be parameterized by lifetimes (type Item<'a>), enabling the lending iterator; OCaml has no lifetime concept.

Complexity: Rust's GAT support has known limitations around lifetime bounds (where Self: 'a is often required); OCaml's parameterized types have no such requirement.

Ergonomics: OCaml's syntax for parameterized associated types is simpler ('a t); Rust requires the full type Item<'a> where Self: 'a declaration.

OCaml Approach

OCaml's module system naturally handles GAT-like patterns through parameterized module types:

module type CONTAINER = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

The type parameter 'a on t provides what Rust calls a GAT. OCaml functors parameterized by such modules achieve full higher-kinded programming without the complexity of GATs — it is a native, well-established feature.

Full Source

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

(* GADTs (Generalized Algebraic Data Types): each constructor can
   fix the type parameter differently. The type carries proof information. *)

(* Classic: typed expression tree *)
type _ expr =
  | Int  : int  -> int expr
  | Bool : bool -> bool expr
  | Add  : int expr * int expr -> int expr
  | If   : bool expr * 'a expr * 'a expr -> 'a expr
  | Eq   : int expr * int expr -> bool expr

(* Type-safe eval: the return type matches the GADT parameter *)
let rec eval : type a. a expr -> a = function
  | Int n          -> n
  | Bool b         -> b
  | Add (l, r)     -> eval l + eval r
  | If (c, t, e)   -> if eval c then eval t else eval e
  | Eq (l, r)      -> eval l = eval r

let () =
  let e1 = Add (Int 3, Int 4) in
  Printf.printf "3 + 4 = %d\n" (eval e1);

  let e2 = If (Bool true, Int 10, Int 20) in
  Printf.printf "if true then 10 else 20 = %d\n" (eval e2);

  let e3 = If (Eq (Int 1, Int 1), Bool true, Bool false) in
  Printf.printf "if 1=1 then true else false = %b\n" (eval e3);

  let e4 = If (Eq (Add (Int 2, Int 3), Int 5), Int 42, Int 0) in
  Printf.printf "if 2+3=5 then 42 else 0 = %d\n" (eval e4)

Deep Comparison

OCaml vs Rust: Gat Basics

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 LendingIterator for a struct StrChunks<'s> that borrows from its source string and yields &'s str slices.

Define a Mappable trait with type Output<U> and implement it for Vec<T>, Option<T>, and Result<T, E>.

Write a GAT-based Stack trait with type Pushed<T> that returns a new stack type with an element pushed, enabling typestate-like operations.

Open Source Repos

functional-rust

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

Rust