Adjunctions & Category Theory

Signature

pub trait Adjunction<F: HKT, U: HKT> {
    fn unit<A: Clone + 'static>(a: A) -> U::Of<F::Of<A>>;
    fn counit<B: 'static>(fub: F::Of<U::Of<B>>) -> B;
}

The trait is bounded by HKT rather than Functor because some right adjoints (like ReaderF<E>) cannot implement the generic Functor trait due to 'static limitations on Box<dyn Fn>.

Laws (Triangle Identities)

// counit(F::fmap(fa, unit)) == fa
// "Going up then back down is identity on F"

// U::fmap(unit(a), counit) == a
// "Going up then back down is identity on U"

Derived Operations

// left_adjunct: (F(A) -> B) -> (A -> U(B))
fn left_adjunct(f, a) = U::fmap(unit(a), f)

// right_adjunct: (A -> U(B)) -> (F(A) -> B)
fn right_adjunct(f, fa) = counit(F::fmap(fa, f))

Instances

How It Works

EnvF<E>::Of<A>   = (E, A)            -- product ("pairing with environment")
ReaderF<E>::Of<A> = Box<dyn Fn(E) -> A>  -- exponential ("function from environment")

unit(a) = |e| (e, a)                   -- embed value into reader of pairs
counit((e, f)) = f(e)                  -- apply the function to the environment

State Monad (U . F = ReaderF . EnvF)

The composed functor ReaderF<E> . EnvF<E> gives Of<A> = Box<dyn Fn(E) → (E, A)> — exactly the State monad, where the environment E is threaded and potentially modified.

use karpal_core::adjunction::*;

// State monad: E -> (E, A) where E is mutable state
let get = state_get::<i32>();               // |e| (e, e)
let put = |s| state_put(s);                  // |_| (s, ())
let modify = state_modify(|e: i32| e + 1);  // |e| (e+1, ())

// Pure wraps a value without touching state
let pure_42 = state_pure::<i32, _>(42);
assert_eq!(pure_42(0), (0, 42));

// Chain sequences state-passing computations
let program = state_chain(
    state_get::<i32>(),
    |x| state_chain(
        state_modify(move |e: i32| e + x),
        |_| state_get::<i32>(),
    ),
);
assert_eq!(program(10), (20, 20));  // get 10, add 10, get 20

Store Comonad (F . U = EnvF . ReaderF)

The composed functor EnvF<E> . ReaderF<E> gives Of<A> = (E, Box<dyn Fn(E) → A>) — the Store comonad, holding a position and a function to look up values.

use karpal_core::adjunction::*;

// Store: (position, lookup_function)
let store: (i32, Box<dyn Fn(i32) -> i32>) =
    (5, Box::new(|e| e * e));

assert_eq!(store_pos(&store), 5);       // current position
assert_eq!(store_peek(3, &store), 9);    // lookup(3) = 9
assert_eq!(store_extract(store), 25);   // lookup(5) = 25 (moves store)

ReaderF<E> cannot implement the generic Functor trait because Box<dyn Fn> requires 'static bounds that the trait signature doesn't allow. Instead, it provides equivalent functionality via inherent methods with 'static bounds on the impl block (the "Lan workaround").

Inherent Methods

impl<E: Clone + 'static> ReaderF<E> {
    fn fmap<A: 'static, B: 'static>(
        fa: Box<dyn Fn(E) -> A>,
        f: impl Fn(A) -> B + 'static,
    ) -> Box<dyn Fn(E) -> B>;

    fn pure<A: Clone + 'static>(a: A) -> Box<dyn Fn(E) -> A>;

    fn chain<A: 'static, B: 'static>(
        fa: Box<dyn Fn(E) -> A>,
        f: impl Fn(A) -> Box<dyn Fn(E) -> B> + 'static,
    ) -> Box<dyn Fn(E) -> B>;

    fn ask() -> Box<dyn Fn(E) -> E>;

    fn local<A: 'static>(
        f: impl Fn(E) -> E + 'static,
        reader: Box<dyn Fn(E) -> A>,
    ) -> Box<dyn Fn(E) -> A>;
}

Examples

use karpal_core::hkt::ReaderF;

// Reader monad: shared read-only environment
let reader = ReaderF::<String>::chain(
    ReaderF::ask(),
    |env: String| ReaderF::pure(env.len()),
);
assert_eq!(reader("hello".to_string()), 5);

State vs Reader: Reader's chain passes the same environment to both computations (|e| f(reader(e))(e)), while State threads modified state (|e| let (e', a) = m(e); f(a)(e')). They are different monads arising from the same adjunction.

Signature

pub struct ComposeF<F, G>(PhantomData<(F, G)>);

impl<F: HKT, G: HKT> HKT for ComposeF<F, G> {
    type Of<T> = F::Of<G::Of<T>>;
}

impl<F: Functor, G: Functor> Functor for ComposeF<F, G> {
    fn fmap<A, B>(fga: F::Of<G::Of<A>>, f: impl Fn(A) -> B) -> F::Of<G::Of<B>> {
        F::fmap(fga, |ga| G::fmap(ga, &f))
    }
}

Examples

use karpal_core::compose::ComposeF;
use karpal_core::functor::Functor;
use karpal_core::hkt::{OptionF, VecF};

// Option<Option<i32>> as a composed functor
let val: Option<Option<i32>> = Some(Some(42));
let result = ComposeF::<OptionF, OptionF>::fmap(val, |x| x + 1);
assert_eq!(result, Some(Some(43)));

// Vec<Option<i32>> -- fmap reaches through both layers
let val: Vec<Option<i32>> = vec![Some(1), None, Some(3)];
let result = ComposeF::<VecF, OptionF>::fmap(val, |x| x * 10);
assert_eq!(result, vec![Some(10), None, Some(30)]);

Functor composition is the key building block for adjunction-derived monads and comonads: the State monad is ComposeF<ReaderF<E>, EnvF<E>> and the Store comonad is ComposeF<EnvF<E>, ReaderF<E>>.

Signature

pub trait DinaturalTransformation<P: HKT2, Q: HKT2> {
    fn transform<A: 'static>(paa: P::P<A, A>) -> Q::P<A, A>;
}

A dinatural transformation is to profunctors what a natural transformation is to functors. Where a natural transformation has components α_A: F(A) → G(A), a dinatural transformation has components α_A: P(A,A) → Q(A,A) that work on the diagonal of a profunctor (both type parameters equal).

Instances

Examples

use karpal_core::dinatural::*;
use karpal_core::hkt::TupleF;

let val: (i32, i32) = (1, 2);
let result = <DinaturalId as DinaturalTransformation<TupleF, TupleF>>
    ::transform::<i32>(val);
assert_eq!(result, (1, 2));

Signature

pub trait End<P: HKT2> {
    fn run<A: 'static>(&self) -> P::P<A, A>;
}

An end is a value that, when asked for any type A, can produce a P(A,A). This is the categorical analogue of forall A. P(A,A) from System F. The End trait is not dyn-compatible (it has a generic method), so implementations must be concrete types.

Ends appear in categorical constructions like the Yoneda lemma (∫_A [A, F(A)] ≅ F) and are the natural setting for parametric polymorphism.

Signature

pub struct Coend<P: HKT2, A> {
    pub value: P::P<A, A>,
}

impl<P: HKT2, A> Coend<P, A> {
    pub fn new(value: P::P<A, A>) -> Self;
    pub fn elim<R>(self, f: impl FnOnce(P::P<A, A>) -> R) -> R;
}

A coend packages a P(A,A) value where the type A is "existentially hidden". Since Rust lacks existential types, A is exposed as a type parameter. The elim method provides CPS-style elimination.

Examples

use karpal_core::coend::Coend;
use karpal_core::hkt::TupleF;

let c = Coend::<TupleF, i32>::new((42, 42));
let sum = c.elim(|(a, b)| a + b);
assert_eq!(sum, 84);

Signature

pub trait ContravariantAdjunction<F: HKT, G: HKT> {
    fn unit<A: Clone + 'static>(a: A) -> G::Of<F::Of<A>>;
    fn counit<B: Clone + 'static>(b: B) -> F::Of<G::Of<B>>;
}

For contravariant functors, the composition G . F is covariant (two contravariants compose to give a covariant functor). The primary instance is the self-adjunction of ContF<R>, which gives the continuation monad.

ContF<R> — The Continuation Functor

pub struct ContF<R>(PhantomData<R>);

// Of<A> = Box<dyn Fn(A) -> R>
// Generalizes PredicateF (which is ContF<bool>)

Instances

ContAdj<R> is self-adjoint: unit and counit are the same operation (|k| k(a)), embedding a value into CPS form.

Continuation Monad Helpers

use karpal_core::adjunction::*;

// Pure: embed a value into CPS
let m = cont_pure::<i32, _>(42);
assert_eq!(cont_run(&*m, |x| x + 1), 43);

// Fmap: transform inside CPS
let mapped = cont_fmap(|x: i32| x * 3, cont_pure(10));
assert_eq!(cont_run(&*mapped, |x| x + 1), 31);  // (10 * 3) + 1

// Chain (bind): sequence CPS computations
let chained = cont_chain(cont_pure(5), |x| cont_pure(x + 10));
assert_eq!(cont_run(&*chained, |x| x * 2), 30);  // (5 + 10) * 2

// call/cc: call-with-current-continuation
let m = cont_call_cc::<i32, i32, i32>(|escape| {
    // escape(10) short-circuits, ignoring the rest
    let escaped = escape(10);
    cont_chain(escaped, |_| cont_pure(999))  // never reached
});
assert_eq!(cont_run(&*m, |x| x), 10);  // not 999!

Signature

/// Type-level functor on profunctors
pub trait ProfunctorFunctor {
    type Applied<P: HKT2>: HKT2;
}

/// Adjunction between profunctor functors
pub trait ProfunctorAdjunction<F: ProfunctorFunctor, U: ProfunctorFunctor> {
    fn unit<P: HKT2, A: 'static, B: 'static>(
        pab: P::P<A, B>,
    ) -> <U::Applied<F::Applied<P>> as HKT2>::P<A, B>;

    fn counit<Q: HKT2, A: 'static, B: 'static>(
        fuqab: <F::Applied<U::Applied<Q>> as HKT2>::P<A, B>,
    ) -> Q::P<A, B>;
}

ProfunctorFunctor maps profunctors to profunctors using GATs as an HKT3-like encoding. A ProfunctorAdjunction witnesses a left/right adjoint pair at the profunctor level, with unit and counit that are natural transformations between profunctors.

Instances

The identity instance maps every profunctor to itself. Non-trivial instances like Pastro ⊣ Tambara require profunctor transformer types and are planned for future phases.

Examples

use karpal_core::adjunction::*;
use karpal_core::hkt::TupleF;

// Identity profunctor adjunction: roundtrip is identity
let val: (i32, String) = (42, "hello".into());
let roundtrip = ProfunctorIdentityAdj::counit::<TupleF, i32, String>(
    ProfunctorIdentityAdj::unit::<TupleF, i32, String>(val.clone()),
);
assert_eq!(roundtrip, val);