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