ExamplesBy LevelBy TopicLearning Paths
383 Advanced
← 382384 →

383: Simulating Higher-Kinded Types with GATs

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "383: Simulating Higher-Kinded Types with GATs" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Higher-Kinded Types (HKTs) let you abstract over type constructors like `Option`, `Vec`, and `Result` — not just concrete types. Key difference from OCaml: 1. **Native vs. simulated**: OCaml supports `'a t` (type constructor abstraction) natively; Rust requires the GAT workaround with `type Mapped<B>`.

Tutorial

The Problem

Higher-Kinded Types (HKTs) let you abstract over type constructors like Option, Vec, and Result — not just concrete types. A Functor typeclass in Haskell captures "any container that can be mapped over" without specifying whether it's a list, maybe, or tree. Rust lacks native HKTs, but Generic Associated Types (GATs, stabilized in Rust 1.65) enable simulation: type Mapped<B> as an associated type lets a trait express "map this container's inner type from A to B."

This pattern appears in functional library design (the futures crate's Output associated type, async-trait patterns) and is the foundation of monadic abstractions used in parser combinators and effect systems.

🎯 Learning Outcomes

  • • Understand what higher-kinded types are and why they matter for generic functional programming
  • • Learn how Rust's Generic Associated Types (GATs) simulate HKT behavior
  • • See the Functor trait implemented for Option, Vec, and Result
  • • Understand the difference between type parameters (concrete types) and type constructors (types that take types)
  • • Learn why Rust chose GATs as the approach to HKT simulation

    • Code Example

    #![allow(clippy::all)]
//! Simulating Higher-Kinded Types with GATs

pub trait Functor {
    type Unwrapped;
    type Mapped<B>;
    fn fmap<B, F: Fn(Self::Unwrapped) -> B>(self, f: F) -> Self::Mapped<B>;
}

impl<A> Functor for Option<A> {
    type Unwrapped = A;
    type Mapped<B> = Option<B>;
    fn fmap<B, F: Fn(A) -> B>(self, f: F) -> Option<B> {
        self.map(f)
    }
}

impl<A> Functor for Vec<A> {
    type Unwrapped = A;
    type Mapped<B> = Vec<B>;
    fn fmap<B, F: Fn(A) -> B>(self, f: F) -> Vec<B> {
        self.into_iter().map(f).collect()
    }
}

impl<A, E> Functor for Result<A, E> {
    type Unwrapped = A;
    type Mapped<B> = Result<B, E>;
    fn fmap<B, F: Fn(A) -> B>(self, f: F) -> Result<B, E> {
        self.map(f)
    }
}

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

    #[test]
    fn test_option_functor() {
        let opt = Some(21);
        let doubled = opt.fmap(|x| x * 2);
        assert_eq!(doubled, Some(42));
    }

    #[test]
    fn test_vec_functor() {
        let v = vec![1, 2, 3];
        let tripled = v.fmap(|x| x * 3);
        assert_eq!(tripled, vec![3, 6, 9]);
    }

    #[test]
    fn test_result_functor() {
        let r: Result<i32, &str> = Ok(10);
        let s = r.fmap(|x| x.to_string());
        assert_eq!(s, Ok("10".to_string()));
    }

    #[test]
    fn test_none_functor() {
        let opt: Option<i32> = None;
        let result = opt.fmap(|x| x * 2);
        assert_eq!(result, None);
    }
}

    Key Differences

  • Native vs. simulated: OCaml supports 'a t (type constructor abstraction) natively; Rust requires the GAT workaround with type Mapped<B>.
  • Ergonomics: OCaml's fmap f opt reads naturally; Rust's opt.fmap(f) works but GAT bounds can become verbose in generic contexts.
  • Monad simulation: OCaml can express bind as naturally as fmap; Rust's GAT approach struggles with bind (flatMap) since Mapped<Mapped<B>> creates problematic nesting.
  • Stability: Rust's GATs were unstable for years and stabilized in 1.65; OCaml has had native HKTs since its inception.

    • OCaml Approach

    OCaml supports HKTs natively through its module system. A Functor module signature contains type 'a t and val fmap : ('a -> 'b) -> 'a t -> 'b t. Implementing for Option is module OptionFunctor = struct type 'a t = 'a option; let fmap f = Option.map f end. The type parameter 'a in 'a t directly expresses the kind * -> * that Rust approximates with GATs. OCaml's approach is simpler and more expressive.

    Full Source

    #![allow(clippy::all)]
//! Simulating Higher-Kinded Types with GATs

pub trait Functor {
    type Unwrapped;
    type Mapped<B>;
    fn fmap<B, F: Fn(Self::Unwrapped) -> B>(self, f: F) -> Self::Mapped<B>;
}

impl<A> Functor for Option<A> {
    type Unwrapped = A;
    type Mapped<B> = Option<B>;
    fn fmap<B, F: Fn(A) -> B>(self, f: F) -> Option<B> {
        self.map(f)
    }
}

impl<A> Functor for Vec<A> {
    type Unwrapped = A;
    type Mapped<B> = Vec<B>;
    fn fmap<B, F: Fn(A) -> B>(self, f: F) -> Vec<B> {
        self.into_iter().map(f).collect()
    }
}

impl<A, E> Functor for Result<A, E> {
    type Unwrapped = A;
    type Mapped<B> = Result<B, E>;
    fn fmap<B, F: Fn(A) -> B>(self, f: F) -> Result<B, E> {
        self.map(f)
    }
}

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

    #[test]
    fn test_option_functor() {
        let opt = Some(21);
        let doubled = opt.fmap(|x| x * 2);
        assert_eq!(doubled, Some(42));
    }

    #[test]
    fn test_vec_functor() {
        let v = vec![1, 2, 3];
        let tripled = v.fmap(|x| x * 3);
        assert_eq!(tripled, vec![3, 6, 9]);
    }

    #[test]
    fn test_result_functor() {
        let r: Result<i32, &str> = Ok(10);
        let s = r.fmap(|x| x.to_string());
        assert_eq!(s, Ok("10".to_string()));
    }

    #[test]
    fn test_none_functor() {
        let opt: Option<i32> = None;
        let result = opt.fmap(|x| x * 2);
        assert_eq!(result, None);
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_option_functor() {
        let opt = Some(21);
        let doubled = opt.fmap(|x| x * 2);
        assert_eq!(doubled, Some(42));
    }

    #[test]
    fn test_vec_functor() {
        let v = vec![1, 2, 3];
        let tripled = v.fmap(|x| x * 3);
        assert_eq!(tripled, vec![3, 6, 9]);
    }

    #[test]
    fn test_result_functor() {
        let r: Result<i32, &str> = Ok(10);
        let s = r.fmap(|x| x.to_string());
        assert_eq!(s, Ok("10".to_string()));
    }

    #[test]
    fn test_none_functor() {
        let opt: Option<i32> = None;
        let result = opt.fmap(|x| x * 2);
        assert_eq!(result, None);
    }
}

    Deep Comparison

    OCaml vs Rust: HKT

    Exercises

  • Applicative functor: Extend the trait to add fn ap<B, F: Fn(Self::Unwrapped) -> B>(self, f: Self::Mapped<F>) -> Self::Mapped<B> and implement it for Option (None when either is None).
  • Custom container: Define a Tree<T> type (leaf or node with two children) and implement Functor for it, applying fmap recursively to transform all leaf values.
  • Foldable trait: Define a Foldable trait with fn fold<B, F: Fn(B, Self::Unwrapped) -> B>(self, init: B, f: F) -> B and implement it for Option and Vec.

    • Open Source Repos

    functional-rust

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

    Rust