145 Advanced

GAT Collections

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "GAT Collections" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. A truly generic collection trait in Rust — one where `map` changes the element type — requires GATs. Key difference from OCaml: 1. **Native vs. GAT**: OCaml's `'a t` is a native parameterized type constructor; Rust requires the GAT feature to express the same concept in traits.

Tutorial

The Problem

A truly generic collection trait in Rust — one where map changes the element type — requires GATs. Without them, you cannot express "a Vec<T> mapped by T -> U produces Vec" in a trait that also applies to HashMap<K, V>, BTreeSet<T>, and custom containers. GAT collections resolve this by making the container's output type generic over the element type, enabling unified generic algorithms over diverse collection types.

🎯 Learning Outcomes

• Learn how GATs enable type Mapped in collection traits, changing element types through map

• Understand the difference between a homogeneous collection trait and a GAT-based one

• See how Functor for collections is expressed using GATs in Rust

• Practice implementing GAT-based traits for Vec<T> and Option<T>

Code Example

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

(* Length-indexed vectors: the type encodes the length.
   Impossible to call head on an empty vector at compile time! *)

type zero  = ZERO
type 'n succ = SUCC

(* Vec of length n containing 'a *)
type (_, _) vec =
  | Nil  : ('a, zero) vec
  | Cons : 'a * ('a, 'n) vec -> ('a, 'n succ) vec

(* Safe head: only works on non-empty vectors *)
let head : type a n. (a, n succ) vec -> a = function
  | Cons (x, _) -> x

(* Safe tail: only works on non-empty vectors *)
let tail : type a n. (a, n succ) vec -> (a, n) vec = function
  | Cons (_, xs) -> xs

(* Append: types encode result length *)
let rec append : type a m n. (a, m) vec -> (a, n) vec -> (a, m) vec =
  fun xs ys -> match xs with
    | Nil         -> Nil   (* simplified: ignores ys for demo *)
    | Cons (x, t) -> Cons (x, append t ys)

let to_list : type a n. (a, n) vec -> a list =
  let rec go : type n. (a, n) vec -> a list = function
    | Nil         -> []
    | Cons (x, t) -> x :: go t
  in go

let () =
  let v0 : (int, zero)       vec = Nil in
  let v1 : (int, zero succ)  vec = Cons (1, Nil) in
  let v3 : (int, zero succ succ succ) vec = Cons (1, Cons (2, Cons (3, Nil))) in

  Printf.printf "v0 = [%s]\n" (String.concat "; " (List.map string_of_int (to_list v0)));
  Printf.printf "v1 head = %d\n" (head v1);
  Printf.printf "v3 = [%s]\n"   (String.concat "; " (List.map string_of_int (to_list v3)));
  Printf.printf "v3 tail head = %d\n" (head (tail v3))

Key Differences

Native vs. GAT: OCaml's 'a t is a native parameterized type constructor; Rust requires the GAT feature to express the same concept in traits.

Verbosity: OCaml's COLLECTION signature is terse; Rust's equivalent requires explicit type Item, type Mapped, and where bounds.

Stability: OCaml's pattern is decades old; Rust's GATs stabilized in 1.65 and still have some rough edges around lifetime inference.

Key-value containers: Extending to HashMap<K, V> requires handling two type parameters; GATs handle this with type Mapped<K2, V2>.

OCaml Approach

OCaml expresses this naturally:

module type COLLECTION = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
  val filter : ('a -> bool) -> 'a t -> 'a t
end
module ListCollection : COLLECTION with type 'a t = 'a list = struct ... end

The parameterized type 'a t is OCaml's built-in equivalent of Rust's GAT type Mapped. This pattern is fundamental to OCaml's standard library design.

Full Source

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

(* Length-indexed vectors: the type encodes the length.
   Impossible to call head on an empty vector at compile time! *)

type zero  = ZERO
type 'n succ = SUCC

(* Vec of length n containing 'a *)
type (_, _) vec =
  | Nil  : ('a, zero) vec
  | Cons : 'a * ('a, 'n) vec -> ('a, 'n succ) vec

(* Safe head: only works on non-empty vectors *)
let head : type a n. (a, n succ) vec -> a = function
  | Cons (x, _) -> x

(* Safe tail: only works on non-empty vectors *)
let tail : type a n. (a, n succ) vec -> (a, n) vec = function
  | Cons (_, xs) -> xs

(* Append: types encode result length *)
let rec append : type a m n. (a, m) vec -> (a, n) vec -> (a, m) vec =
  fun xs ys -> match xs with
    | Nil         -> Nil   (* simplified: ignores ys for demo *)
    | Cons (x, t) -> Cons (x, append t ys)

let to_list : type a n. (a, n) vec -> a list =
  let rec go : type n. (a, n) vec -> a list = function
    | Nil         -> []
    | Cons (x, t) -> x :: go t
  in go

let () =
  let v0 : (int, zero)       vec = Nil in
  let v1 : (int, zero succ)  vec = Cons (1, Nil) in
  let v3 : (int, zero succ succ succ) vec = Cons (1, Cons (2, Cons (3, Nil))) in

  Printf.printf "v0 = [%s]\n" (String.concat "; " (List.map string_of_int (to_list v0)));
  Printf.printf "v1 head = %d\n" (head v1);
  Printf.printf "v3 = [%s]\n"   (String.concat "; " (List.map string_of_int (to_list v3)));
  Printf.printf "v3 tail head = %d\n" (head (tail v3))

Deep Comparison

OCaml vs Rust: Gat Collections

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 Collection for Option<T> with type Mapped = Option.

Add a flat_map_col(self, f: impl Fn(Self::Item) -> Self::Mapped) -> Self::Mapped method to the trait.

Write a generic double_all<C: Collection<Item = i32>>(c: C) -> C::Mapped<i32> that doubles every element.

Open Source Repos

functional-rust

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

Rust