karpal_recursion/algebra.rs
1/// Type aliases documenting the various algebra and coalgebra forms
2/// used in recursion schemes.
3///
4/// These are provided for documentation and pedagogy. The actual scheme
5/// functions accept `impl Fn(...)` parameters directly, which is more
6/// ergonomic than working with trait objects.
7///
8/// # Algebra family (folds)
9///
10/// - **Algebra**: `F<A> -> A` — basic fold (catamorphism)
11/// - **RAlgebra**: `F<(Fix<F>, A)> -> A` — fold with original subterms (paramorphism)
12/// - **CVAlgebra**: `F<Cofree<F, A>> -> A` — fold with history (histomorphism)
13///
14/// # Coalgebra family (unfolds)
15///
16/// - **Coalgebra**: `A -> F<A>` — basic unfold (anamorphism)
17/// - **RCoalgebra**: `A -> F<Either<Fix<F>, A>>` — unfold with early stop (apomorphism)
18/// - **CVCoalgebra**: `A -> F<Free<F, A>>` — multi-step unfold (futumorphism)
19///
20/// # Composite
21///
22/// - **Chronomorphism**: CVCoalgebra + CVAlgebra (futu ; histo)
23/// - **Zygomorphism**: Algebra + auxiliary Algebra (fold with helper)
24use karpal_core::hkt::HKT;
25
26use crate::either::Either;
27use crate::fix::Fix;
28
29#[cfg(feature = "std")]
30use std::boxed::Box;
31
32#[cfg(all(not(feature = "std"), feature = "alloc"))]
33use alloc::boxed::Box;
34
35/// `F<A> -> A` — an F-algebra, used in catamorphism.
36pub type Algebra<F, A> = Box<dyn Fn(<F as HKT>::Of<A>) -> A>;
37
38/// `A -> F<A>` — an F-coalgebra, used in anamorphism.
39pub type Coalgebra<F, A> = Box<dyn Fn(A) -> <F as HKT>::Of<A>>;
40
41/// `F<(Fix<F>, A)> -> A` — an R-algebra, used in paramorphism.
42pub type RAlgebra<F, A> = Box<dyn Fn(<F as HKT>::Of<(Fix<F>, A)>) -> A>;
43
44/// `A -> F<Either<Fix<F>, A>>` — an R-coalgebra, used in apomorphism.
45pub type RCoalgebra<F, A> = Box<dyn Fn(A) -> <F as HKT>::Of<Either<Fix<F>, A>>>;