karpal-recursion 0.6.0

Recursion schemes (cata, ana, hylo, para, apo, histo, futu, zygo, chrono) for the Industrial Algebra ecosystem
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// Copyright (C) 2026 Industrial Algebra
// SPDX-License-Identifier: Apache-2.0

/// Type aliases documenting the various algebra and coalgebra forms
/// used in recursion schemes.
///
/// These are provided for documentation and pedagogy. The actual scheme
/// functions accept `impl Fn(...)` parameters directly, which is more
/// ergonomic than working with trait objects.
///
/// # Algebra family (folds)
///
/// - **Algebra**: `F<A> -> A` — basic fold (catamorphism)
/// - **RAlgebra**: `F<(Fix<F>, A)> -> A` — fold with original subterms (paramorphism)
/// - **CVAlgebra**: `F<Cofree<F, A>> -> A` — fold with history (histomorphism)
///
/// # Coalgebra family (unfolds)
///
/// - **Coalgebra**: `A -> F<A>` — basic unfold (anamorphism)
/// - **RCoalgebra**: `A -> F<Either<Fix<F>, A>>` — unfold with early stop (apomorphism)
/// - **CVCoalgebra**: `A -> F<Free<F, A>>` — multi-step unfold (futumorphism)
///
/// # Composite
///
/// - **Chronomorphism**: CVCoalgebra + CVAlgebra (futu ; histo)
/// - **Zygomorphism**: Algebra + auxiliary Algebra (fold with helper)
use karpal_core::hkt::HKT;

use crate::either::Either;
use crate::fix::Fix;

#[cfg(feature = "std")]
use std::boxed::Box;

#[cfg(all(not(feature = "std"), feature = "alloc"))]
use alloc::boxed::Box;

/// `F<A> -> A` — an F-algebra, used in catamorphism.
pub type Algebra<F, A> = Box<dyn Fn(<F as HKT>::Of<A>) -> A>;

/// `A -> F<A>` — an F-coalgebra, used in anamorphism.
pub type Coalgebra<F, A> = Box<dyn Fn(A) -> <F as HKT>::Of<A>>;

/// `F<(Fix<F>, A)> -> A` — an R-algebra, used in paramorphism.
pub type RAlgebra<F, A> = Box<dyn Fn(<F as HKT>::Of<(Fix<F>, A)>) -> A>;

/// `A -> F<Either<Fix<F>, A>>` — an R-coalgebra, used in apomorphism.
pub type RCoalgebra<F, A> = Box<dyn Fn(A) -> <F as HKT>::Of<Either<Fix<F>, A>>>;