134: Higher-Kinded Types Simulation

Difficulty: ⭐⭐⭐ Level: Advanced Write generic algorithms that work over any container — `Option`, `Vec`, `Result` — without duplicating code, by simulating the higher-kinded types Rust doesn't natively support.

The Problem This Solves

In functional programming, a `Functor` is any container you can `map` over. `Option::map`, `Vec::iter().map()`, `Result::map` — all the same pattern, different containers. In OCaml or Haskell you can write a single `double_all` function that works for any functor, parameterized over the container type itself. Rust doesn't support higher-kinded types natively. You can't write `fn double_all<F<_>>(xs: F<i32>) -> F<i32>` — Rust doesn't allow type-level functions (types that take types and return types). So you end up copy-pasting: one `double_all_option`, one `double_all_vec`, one `double_all_result`. That's not reuse. The simulation uses a technique called defunctionalization: instead of parameterizing over `F<_>` directly, you introduce a marker type `OptionHKT` and a trait that maps `T` to `F<T>` via an associated type. It's indirect, but it works — you get genuinely generic code over container type.

The Intuition

The core trick: instead of `F<T>`, write `F::Applied<T>`. Define a trait `HKT` with an associated type `Applied<T>`. For `OptionHKT`, `Applied<T>` is `Option<T>`. For `VecHKT`, `Applied<T>` is `Vec<T>`. Now your generic function takes `F: HKT` and works with `F::Applied<i32>` — which resolves to `Option<i32>` or `Vec<i32>` depending on the type argument. Layer `Functor` on top of `HKT` to add the `map` operation. Layer `Monad` on top of `Functor` to add `flat_map` (the ability to chain operations that might fail or expand). Each new container type just needs an `impl` of these traits, and all generic algorithms work for free.

How It Works in Rust

// Step 1: HKT trait — the "applied" trick
trait HKT {
 type Applied<T>;  // GAT (generic associated type): maps T → Container<T>
}

// Step 2: Marker types for each container
struct OptionHKT;
impl HKT for OptionHKT {
 type Applied<T> = Option<T>;  // OptionHKT::Applied<i32> = Option<i32>
}

struct VecHKT;
impl HKT for VecHKT {
 type Applied<T> = Vec<T>;     // VecHKT::Applied<i32> = Vec<i32>
}

// Step 3: Functor — generic map over any HKT
trait Functor: HKT {
 fn map<A, B>(fa: Self::Applied<A>, f: impl Fn(A) -> B) -> Self::Applied<B>;
}

impl Functor for OptionHKT {
 fn map<A, B>(fa: Option<A>, f: impl Fn(A) -> B) -> Option<B> { fa.map(f) }
}

impl Functor for VecHKT {
 fn map<A, B>(fa: Vec<A>, f: impl Fn(A) -> B) -> Vec<B> {
     fa.into_iter().map(f).collect()
 }
}

// Step 4: Write ONE function that works for any Functor
fn double_all<F: Functor>(xs: F::Applied<i32>) -> F::Applied<i32> {
 F::map(xs, |x| x * 2)
}

// Step 5: Monad adds flat_map (sequencing, chaining)
trait Monad: Functor {
 fn pure<A>(a: A) -> Self::Applied<A>;
 fn flat_map<A, B>(fa: Self::Applied<A>, f: impl Fn(A) -> Self::Applied<B>) -> Self::Applied<B>;
}

impl Monad for OptionHKT {
 fn pure<A>(a: A) -> Option<A> { Some(a) }
 fn flat_map<A, B>(fa: Option<A>, f: impl Fn(A) -> Option<B>) -> Option<B> { fa.and_then(f) }
}

Usage:

// Same function, different containers — no duplication
let doubled_vec = double_all::<VecHKT>(vec![1, 2, 3]);   // [2, 4, 6]
let doubled_opt = double_all::<OptionHKT>(Some(21));       // Some(42)

// Monadic chaining: safe division then safe sqrt
fn safe_div(a: i32, b: i32) -> Option<i32> { if b == 0 { None } else { Some(a / b) } }

let result = OptionHKT::flat_map(Some(10), |x|
 OptionHKT::flat_map(safe_div(x, 2), safe_sqrt)
);  // Some(2.236...)

What This Unlocks

Generic combinators — write `sequence`, `traverse`, `zip_with` once and use them with any container that implements `Functor`/`Monad`.
Testing abstractions — implement a test container type (`IdentityHKT`) that runs without effects, letting you unit-test code that would normally use `Future` or `IO`.
Effect systems — advanced libraries simulate effect polymorphism using this technique, letting the same business logic run synchronously or asynchronously.

Key Differences

Concept	OCaml	Rust
Higher-kinded types	Native: `module type FUNCTOR = sig type 'a t val map : ... end`	Simulated: `trait HKT { type Applied<T>; }` via GATs
Functor definition	Module type with `type 'a t`	Trait `Functor: HKT` with `fn map`
Generic algorithms	Module functor `module DoubleAll(F: FUNCTOR)`	Generic function `fn double_all<F: Functor>`
Monad	`MONAD` module type extending `FUNCTOR`	Trait `Monad: Functor` with `pure` and `flat_map`

// Example 134: Higher-Kinded Types Simulation
// Rust doesn't have HKTs, but we can simulate them

// Approach 1: HKT trait pattern (defunctionalization)
trait HKT {
    type Applied<T>;
}

struct OptionHKT;
impl HKT for OptionHKT {
    type Applied<T> = Option<T>;
}

struct VecHKT;
impl HKT for VecHKT {
    type Applied<T> = Vec<T>;
}

// Functor trait using HKT
trait Functor: HKT {
    fn map<A, B>(fa: Self::Applied<A>, f: impl Fn(A) -> B) -> Self::Applied<B>;
}

impl Functor for OptionHKT {
    fn map<A, B>(fa: Option<A>, f: impl Fn(A) -> B) -> Option<B> {
        fa.map(f)
    }
}

impl Functor for VecHKT {
    fn map<A, B>(fa: Vec<A>, f: impl Fn(A) -> B) -> Vec<B> {
        fa.into_iter().map(f).collect()
    }
}

// Approach 2: Monad simulation
trait Monad: Functor {
    fn pure<A>(a: A) -> Self::Applied<A>;
    fn flat_map<A, B>(fa: Self::Applied<A>, f: impl Fn(A) -> Self::Applied<B>) -> Self::Applied<B>;
}

impl Monad for OptionHKT {
    fn pure<A>(a: A) -> Option<A> { Some(a) }
    fn flat_map<A, B>(fa: Option<A>, f: impl Fn(A) -> Option<B>) -> Option<B> {
        fa.and_then(f)
    }
}

impl Monad for VecHKT {
    fn pure<A>(a: A) -> Vec<A> { vec![a] }
    fn flat_map<A, B>(fa: Vec<A>, f: impl Fn(A) -> Vec<B>) -> Vec<B> {
        fa.into_iter().flat_map(f).collect()
    }
}

// Approach 3: Generic algorithms over functors
fn double_all<F: Functor>(xs: F::Applied<i32>) -> F::Applied<i32> {
    F::map(xs, |x| x * 2)
}

fn increment_all<F: Functor>(xs: F::Applied<i32>) -> F::Applied<i32> {
    F::map(xs, |x| x + 1)
}

// Monadic composition
fn safe_div(a: i32, b: i32) -> Option<i32> {
    if b == 0 { None } else { Some(a / b) }
}

fn safe_sqrt(x: i32) -> Option<f64> {
    if x < 0 { None } else { Some((x as f64).sqrt()) }
}

fn main() {
    // Functor usage
    let doubled_vec = double_all::<VecHKT>(vec![1, 2, 3]);
    println!("Doubled vec: {:?}", doubled_vec);

    let doubled_opt = double_all::<OptionHKT>(Some(21));
    println!("Doubled opt: {:?}", doubled_opt);

    // Monad usage
    let result = OptionHKT::flat_map(Some(10), |x| safe_div(x, 2));
    println!("10 / 2 = {:?}", result);

    let result = OptionHKT::flat_map(Some(10), |x|
        OptionHKT::flat_map(safe_div(x, 2), |y| safe_sqrt(y))
    );
    println!("sqrt(10/2) = {:?}", result);
}

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

    #[test]
    fn test_option_functor() {
        assert_eq!(OptionHKT::map(Some(5), |x| x * 2), Some(10));
        assert_eq!(OptionHKT::map(None::<i32>, |x| x * 2), None);
    }

    #[test]
    fn test_vec_functor() {
        assert_eq!(VecHKT::map(vec![1, 2, 3], |x| x + 1), vec![2, 3, 4]);
    }

    #[test]
    fn test_double_all_generic() {
        assert_eq!(double_all::<VecHKT>(vec![1, 2, 3]), vec![2, 4, 6]);
        assert_eq!(double_all::<OptionHKT>(Some(5)), Some(10));
    }

    #[test]
    fn test_option_monad() {
        assert_eq!(OptionHKT::flat_map(Some(10), |x| safe_div(x, 2)), Some(5));
        assert_eq!(OptionHKT::flat_map(Some(10), |x| safe_div(x, 0)), None);
        assert_eq!(OptionHKT::flat_map(None, |x: i32| safe_div(x, 2)), None);
    }

    #[test]
    fn test_vec_monad() {
        let result = VecHKT::flat_map(vec![1, 2, 3], |x| vec![x, x * 10]);
        assert_eq!(result, vec![1, 10, 2, 20, 3, 30]);
    }

    #[test]
    fn test_monad_pure() {
        assert_eq!(OptionHKT::pure(42), Some(42));
        assert_eq!(VecHKT::pure(42), vec![42]);
    }
}

(* Example 134: Higher-Kinded Types Simulation *)
(* OCaml has natural HKTs via module system *)

(* Approach 1: Functor typeclass via modules *)
module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

module ListFunctor : FUNCTOR with type 'a t = 'a list = struct
  type 'a t = 'a list
  let map = List.map
end

module OptionFunctor : FUNCTOR with type 'a t = 'a option = struct
  type 'a t = 'a option
  let map f = function None -> None | Some x -> Some (f x)
end

(* Approach 2: Monad via modules *)
module type MONAD = sig
  type 'a t
  val return_ : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end

module OptionMonad : MONAD with type 'a t = 'a option = struct
  type 'a t = 'a option
  let return_ x = Some x
  let bind m f = match m with None -> None | Some x -> f x
end

module ListMonad : MONAD with type 'a t = 'a list = struct
  type 'a t = 'a list
  let return_ x = [x]
  let bind m f = List.concat_map f m
end

(* Approach 3: Generic algorithms over functors *)
module DoubleAll (F : FUNCTOR) = struct
  let double_all xs = F.map (fun x -> x * 2) xs
end

module DoubleList = DoubleAll(ListFunctor)
module DoubleOption = DoubleAll(OptionFunctor)

(* Tests *)
let () =
  assert (ListFunctor.map (fun x -> x + 1) [1;2;3] = [2;3;4]);
  assert (OptionFunctor.map (fun x -> x * 2) (Some 5) = Some 10);
  assert (OptionFunctor.map (fun x -> x * 2) None = None);
  assert (OptionMonad.bind (Some 5) (fun x -> Some (x * 2)) = Some 10);
  assert (OptionMonad.bind None (fun x -> Some (x * 2)) = None);
  assert (ListMonad.bind [1;2;3] (fun x -> [x; x*10]) = [1;10;2;20;3;30]);
  assert (DoubleList.double_all [1;2;3] = [2;4;6]);
  assert (DoubleOption.double_all (Some 5) = Some 10);
  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: Higher-Kinded Types Simulation

OCaml (native HKT)

🐪 Show OCaml equivalent

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

module OptionFunctor : FUNCTOR with type 'a t = 'a option = struct
type 'a t = 'a option
let map f = function None -> None | Some x -> Some (f x)
end

(* Generic over any functor *)
module DoubleAll (F : FUNCTOR) = struct
let double_all xs = F.map (fun x -> x * 2) xs
end

Rust (simulated HKT)

trait HKT { type Applied<T>; }

struct OptionHKT;
impl HKT for OptionHKT { type Applied<T> = Option<T>; }

trait Functor: HKT {
 fn map<A, B>(fa: Self::Applied<A>, f: impl Fn(A) -> B) -> Self::Applied<B>;
}

// Generic over any functor
fn double_all<F: Functor>(xs: F::Applied<i32>) -> F::Applied<i32> {
 F::map(xs, |x| x * 2)
}