Recursion Schemes

Definition

pub struct Fix<F: HKT>(Rc<F::Of<Fix<F>>>);

// Unconditional Clone via Rc reference counting
impl<F: HKT> Clone for Fix<F> { ... }

pub type Mu<F> = Fix<F>;

Key Methods

// Wrap one layer
Fix::new(f: F::Of<Fix<F>>) -> Fix<F>

// Unwrap one layer (consuming)
fix.unfix() -> F::Of<Fix<F>>  // where F::Of<Fix<F>>: Clone

// Borrow one layer
fix.unfix_ref() -> &F::Of<Fix<F>>

Design: Rc vs Box

Fix uses Rc instead of Box for indirection. This makes Fix<F>: Clone unconditional (just a reference count bump), which is essential for paramorphism — it needs to both preserve and consume each subterm. Rust's trait solver cannot prove coinductive Clone bounds like Fix<OptionF>: Clone ↔ Option<Fix<OptionF>>: Clone, so Box would make Clone impossible.

Example: Natural Numbers

use karpal_recursion::{Fix, cata, ana};
use karpal_core::hkt::OptionF;

// None = Zero, Some(n) = Succ(n)
let three: Fix<OptionF> = Fix::new(Some(Fix::new(Some(Fix::new(None)))));

// Or build with ana:
let five: Fix<OptionF> = ana(
    |n: u32| if n == 0 { None } else { Some(n - 1) },
    5,
);

// Fold with cata:
let count = cata::<OptionF, u32>(
    |layer| match layer {
        None => 0,
        Some(n) => n + 1,
    },
    five,
);
assert_eq!(count, 5);

Definition

pub struct Nu<F: HKT, Seed> {
    pub seed: Seed,
    pub coalgebra: Box<dyn Fn(&Seed) -> F::Of<Seed>>,
}

Key Methods

Nu::new(seed, coalgebra) -> Nu<F, Seed>
nu.observe() -> F::Of<Seed>   // apply coalgebra once
nu.to_fix() -> Fix<F>         // fully unfold via ana

Example

use karpal_recursion::Nu;
use karpal_core::hkt::OptionF;

let countdown = Nu::<OptionF, u32>::new(3, |&s| {
    if s == 0 { None } else { Some(s - 1) }
});
assert_eq!(countdown.observe(), Some(2));

Signature

pub fn cata<F: HKT + Functor, A>(
    alg: impl Fn(F::Of<A>) -> A,
    fix: Fix<F>,
) -> A

Example: Sum Natural Numbers

let n = ana(|s: u32| if s == 0 { None } else { Some(s - 1) }, 5);
let sum = cata::<OptionF, u32>(
    |layer| match layer {
        None => 0,
        Some(acc) => acc + 1,
    },
    n,
);
assert_eq!(sum, 5);

Laws

• cata(Fix::new, x) == x — folding with the constructor is identity

Signature

pub fn ana<F: HKT + Functor, A>(
    coalg: impl Fn(A) -> F::Of<A>,
    seed: A,
) -> Fix<F>

Example: Build Natural Numbers

let three: Fix<OptionF> = ana(
    |n: u32| if n == 0 { None } else { Some(n - 1) },
    3,
);

Laws

• cata(alg, ana(coalg, seed)) == hylo(alg, coalg, seed)

Signature

pub fn hylo<F: HKT + Functor, A, B>(
    alg: impl Fn(F::Of<B>) -> B,
    coalg: impl Fn(A) -> F::Of<A>,
    seed: A,
) -> B

Key Property

hylo(alg, coalg, seed) == cata(alg, ana(coalg, seed)) but more efficient — the intermediate data structure is "deforested" away.

Signature

pub fn para<F: HKT + Functor, A>(
    alg: impl Fn(F::Of<(Fix<F>, A)>) -> A,
    fix: Fix<F>,
) -> A

Example: Factorial

let factorial = para::<OptionF, u64>(
    |layer| match layer {
        None => 1,           // 0! = 1
        Some((sub, acc)) => {
            let n = count(&sub) + 1;  // read current number from subterm
            (n as u64) * acc
        }
    },
    nat(5),
);
assert_eq!(factorial, 120);

Laws

• When ignoring the Fix<F> subterm, para degenerates to cata

Signature

pub fn apo<F: HKT + Functor, A>(
    coalg: impl Fn(A) -> F::Of<Either<Fix<F>, A>>,
    seed: A,
) -> Fix<F>

Key Idea

Either::Right(seed) continues unfolding, Either::Left(fix) embeds an already-built subtree directly. When always returning Right, apo degenerates to ana.

Signature

pub fn histo<F: HKT + Functor, A>(
    alg: impl Fn(&F::Of<Cofree<F, A>>) -> A,
    fix: Fix<F>,
) -> A

Example: Fibonacci

let fib = histo::<OptionF, u64>(
    |layer| match layer {
        None => 0,                      // fib(0) = 0
        Some(cofree) => {
            let prev = cofree.head;      // fib(n-1)
            match cofree.tail.as_ref() {
                None => 1,               // fib(1) = 1
                Some(gc) => prev + gc.head,  // fib(n-1) + fib(n-2)
            }
        }
    },
    nat(10),
);
assert_eq!(fib, 55);

Design Note

The algebra takes &F::Of<Cofree<F, A>> (a reference) rather than ownership. This avoids needing Clone on the recursive Cofree structure, which Rust's trait solver cannot prove coinductively.

Signature

pub fn futu<F: HKT + Functor, A>(
    coalg: impl Fn(A) -> F::Of<Free<F, A>>,
    seed: A,
) -> Fix<F>

Key Idea

Free::Pure(seed) continues with one more coalgebra application. Free::Roll(f) injects multiple layers at once. When always returning Pure, futu degenerates to ana.

Signature

pub fn zygo<F: HKT + Functor, A, B>(
    aux: impl Fn(F::Of<B>) -> B,
    alg: impl Fn(F::Of<(B, A)>) -> A,
    fix: Fix<F>,
) -> A
where F::Of<(B, A)>: Clone

Key Idea

Two algebras run simultaneously: aux computes a helper value B at each layer, and alg has access to both B and the primary result A from sub-structures.

Signature

pub fn chrono<F: HKT + Functor, A, B>(
    alg: impl Fn(&F::Of<Cofree<F, B>>) -> B,
    coalg: impl Fn(A) -> F::Of<Free<F, A>>,
    seed: A,
) -> B

Key Idea

Conceptually chrono = histo . futu — multi-step unfolding with history-aware folding — but computed in a single pass without building an intermediate Fix.

Definition

pub enum Either<L, R> {
    Left(L),
    Right(R),
}

// Methods: either, map_left, map_right