Home > Architecture

Architecture

This page explains the core design decisions behind Karpal: how it encodes higher-kinded types in Rust, the full trait hierarchy, and the Static Land pattern that makes it all work within Rust's type system.

HKT Encoding

The problem

Rust has no native higher-kinded types. You cannot write a trait that is generic over a type constructor like Option or Vec — only over concrete types like Option<i32>. This means there is no built-in way to express "for any container F, give me an fmap that works on F<A>."

The GAT solution

Karpal encodes type constructors as marker types that implement a trait with a Generic Associated Type (GAT). The HKT trait acts as a type-level function: given a type T, it produces Self::Of<T>.

/// Higher-Kinded Type encoding via GATs.
///
/// A type implementing `HKT` acts as a type-level function:
/// given a type `T`, it produces `Self::Of<T>`.
pub trait HKT {
    type Of<T>;
}

Each standard container gets a zero-sized marker type that maps Of<T> to the real type:

/// Type constructor for `Option<T>`.
pub struct OptionF;

impl HKT for OptionF {
    type Of<T> = Option<T>;
}

/// Type constructor for `Result<T, E>` (fixed error type `E`).
pub struct ResultF<E> {
    _marker: PhantomData<E>,
}

impl<E> HKT for ResultF<E> {
    type Of<T> = Result<T, E>;
}

/// Type constructor for `Vec<T>` (alloc-gated).
#[cfg(any(feature = "std", feature = "alloc"))]
pub struct VecF;

#[cfg(any(feature = "std", feature = "alloc"))]
impl HKT for VecF {
    type Of<T> = Vec<T>;
}

Two-parameter HKT

For types with two type parameters — bifunctors and profunctors — Karpal provides HKT2:

/// Two-parameter type constructor (HKT for bifunctors / profunctors).
pub trait HKT2 {
    type P<A, B>;
}

/// Result as a bifunctor (both parameters vary).
pub struct ResultBF;

impl HKT2 for ResultBF {
    type P<A, B> = Result<B, A>;
}

/// Tuple as a bifunctor.
pub struct TupleF;

impl HKT2 for TupleF {
    type P<A, B> = (A, B);
}

Tradeoffs

Trait Hierarchy

The diagram below shows the full trait hierarchy implemented in karpal-core, karpal-profunctor, and karpal-arrow. Arrows point from supertrait to subtrait. Dashed borders indicate blanket implementations (no manual impl needed).

Key: Solid borders are standard traits. Dashed borders indicate blanket implementations — Monad is automatically derived for any type that implements both Applicative and Chain, and Alternative for Applicative + Plus.

The Static Land Pattern

Karpal uses associated functions on marker types, not methods on values. Instead of calling some_value.fmap(f), you write:

// Karpal's Static Land style
let result = OptionF::fmap(Some(42), |x| x + 1);

// NOT the method-on-value style (not possible in Karpal)
// let result = Some(42).fmap(|x| x + 1);

Why this approach?

Rust's trait coherence rules (the orphan rule) prevent you from implementing a foreign trait on a foreign type. Since Option is defined in std and Functor is defined in Karpal, you cannot write impl Functor for Option<T> directly.

The marker-type approach sidesteps this entirely. OptionF is owned by Karpal, so Karpal can freely implement any trait on it. The HKT GAT bridges the gap back to the actual container type via the Of<T> associated type.

Comparison with other ecosystems

Design Decisions

no_std first

karpal-core, karpal-profunctor, and karpal-arrow compile without std. Types that require heap allocation — VecF, NonEmptyVecF, PredicateF, StoreF, TracedF — are gated behind the alloc or std feature flags. This makes Karpal usable in embedded and no_std environments.

Nightly edition 2024

The toolchain is pinned to nightly via rust-toolchain.toml. While GATs themselves stabilized in Rust 1.65, Karpal also relies on use<> precise-capture syntax (edition 2024) and the alloc feature gate for no_std builds. The nightly pin ensures all contributors use the same compiler.

fn pointers in optics

The Lens struct stores plain function pointers rather than closures:

pub struct Lens<S, T, A, B> {
    getter: fn(&S) -> A,
    setter: fn(S, B) -> T,
}

This keeps Lens Copy-able and avoids lifetime complications. When lenses are composed via Lens::then(), the result is a ComposedLens that uses Box<dyn Fn> closures instead, since closure composition cannot produce fn pointers.

'static bounds on Box<dyn Fn>

Types whose inner representation is a boxed closure — PredicateF, FnP, FnA, KleisliF, CokleisliF, StoreF, TracedF — require 'static bounds. This is an inherent limitation of Box<dyn Fn> in Rust. As a consequence, StoreF and TracedF cannot implement the generic Functor trait (whose signature does not carry a 'static bound); they provide their own fmap through the Extend/Comonad implementation instead.

Blanket implementations

Where the theory permits, Karpal uses blanket impls to eliminate boilerplate:

/// Monad: Applicative + Chain with no extra methods (blanket impl).
pub trait Monad: Applicative + Chain {}

impl<F: Applicative + Chain> Monad for F {}

Any marker type that implements both Applicative and Chain is automatically a Monad. The same pattern applies to Alternative (= Applicative + Plus). Implementors only need to provide the primitive operations; the composed abstractions come for free.

Property-based law testing

Every algebraic trait in Karpal has proptest-based law tests that verify the required algebraic identities hold. For example, the Functor laws:

proptest! {
    #[test]
    fn option_identity(x in any::<Option<i32>>()) {
        // Identity law: fmap(id, fa) == fa
        let result = OptionF::fmap(x.clone(), |a| a);
        prop_assert_eq!(result, x);
    }

    #[test]
    fn option_composition(x in any::<Option<i32>>()) {
        // Composition law: fmap(g . f, fa) == fmap(g, fmap(f, fa))
        let f = |a: i32| a.wrapping_add(1);
        let g = |a: i32| a.wrapping_mul(2);
        let left = OptionF::fmap(x.clone(), |a| g(f(a)));
        let right = OptionF::fmap(OptionF::fmap(x, f), g);
        prop_assert_eq!(left, right);
    }
}

This approach catches subtle bugs that unit tests miss — such as associativity violations in Semigroup implementations or distributivity failures in Alternative.