383: Simulating Higher-Kinded Types with GATs

The Problem This Solves

// What you WANT to write:
fn double_all<F: Functor>(container: F<i32>) -> F<i32> {
 container.map(|x| x * 2)
}

// But Rust says: ERROR — can't use `F<i32>` (F is not a type constructor)

The Intuition

• A type is a specific box with specific contents: `Option<i32>`, `Vec<String>`.
• A type constructor is the box shape without contents yet: `Option<_>`, `Vec<_>`.

trait Functor {
 type Unwrapped;         // the A in Container<A>
 type Mapped<B>;         // what this becomes when you map A -> B
 
 fn map<B>(self, f: fn(Self::Unwrapped) -> B) -> Self::Mapped<B>;
}

• `Option<A>` says `Mapped<B> = Option<B>`
• `Vec<A>` says `Mapped<B> = Vec<B>`
• `Result<A, E>` says `Mapped<B> = Result<B, E>`

How It Works in Rust

// The Functor trait — simulating HKT via GATs
trait Functor {
 type Unwrapped;           // the inner type A
 type Mapped<B>;           // GAT: what we become after mapping to B

 fn map<B, F: Fn(Self::Unwrapped) -> B>(self, f: F) -> Self::Mapped<B>;
}

// Implementation for Option<A>
impl<A> Functor for Option<A> {
 type Unwrapped = A;
 type Mapped<B> = Option<B>;  // Option<A>.map(...) -> Option<B>

 fn map<B, F: Fn(A) -> B>(self, f: F) -> Option<B> {
     self.map(f)  // delegate to Option's built-in map
 }
}

// Implementation for Vec<A>
impl<A> Functor for Vec<A> {
 type Unwrapped = A;
 type Mapped<B> = Vec<B>;  // Vec<A>.map(...) -> Vec<B>

 fn map<B, F: Fn(A) -> B>(self, f: F) -> Vec<B> {
     self.into_iter().map(f).collect()
 }
}

// Implementation for Result<A, E>
impl<A, E> Functor for Result<A, E> {
 type Unwrapped = A;
 type Mapped<B> = Result<B, E>;  // Result<A,E>.map(...) -> Result<B,E>

 fn map<B, F: Fn(A) -> B>(self, f: F) -> Result<B, E> {
     self.map(f)
 }
}

fn main() {
 // All three use the SAME Functor trait — generic, not repeated
 let opt: Option<i32> = Some(21);
 let doubled = Functor::map(opt, |x| x * 2);  // Some(42)

 let v: Vec<i32> = vec![1, 2, 3, 4];
 let tripled = Functor::map(v, |x| x * 3);    // [3, 6, 9, 12]

 let r: Result<i32, &str> = Ok(10);
 let stringified = Functor::map(r, |x| x.to_string()); // Ok("10")
}

What This Unlocks

• Generic combinators: Write adapters, validators, transformers that work for `Option`, `Vec`, and `Result` through one trait implementation — eliminates copy-paste.
• Monad-like abstractions: GATs are the stepping stone toward simulating `Monad` traits (with `bind`/`flat_map`) generically — used in libraries like `higher` and `fp-core`.
• Understanding Rust's future: HKT has been a long-requested Rust feature. GATs are the current approximation. Understanding GATs deeply prepares you for the type-level abstractions that Rust is moving toward.

Key Differences