Function fold 

pub fn fold<F, A>(t: Fix<F>, alg: impl FnMut(F::Applied<A>) -> A) -> A
where
    F: Functor,

A catamorphism: fold a recursive structure using an F-algebra.

Given an algebra alg : F(A) → A, this produces a function Fix<F> → A that recursively applies the algebra from the leaves up.

Stack Safety

This implementation uses direct recursion. The risk of stack overflow is proportional to the recursion depth, not the total size of the structure.

• Balanced trees: Typically safe (depth ≈ log(n))
• Skewed structures (e.g., long linked lists): May overflow

Stack overflow typically occurs around ~10k frames on common platforms, but this varies. For very deep structures, consider using the stacker crate or an iterative approach.

Example

use algebra_core::fix::{TypeApp, Functor, Fix, fold};

// Expression tree: Expr = Lit(i32) | Add(Expr, Expr)
enum ExprF<X> {
    Lit(i32),
    Add(X, X),
}

struct ExprTag;

impl TypeApp for ExprTag {
    type Applied<X> = ExprF<X>;
}

impl Functor for ExprTag {
    fn fmap<X, Y, G>(fx: ExprF<X>, mut g: G) -> ExprF<Y>
    where
        G: FnMut(X) -> Y,
    {
        match fx {
            ExprF::Lit(n) => ExprF::Lit(n),
            ExprF::Add(l, r) => ExprF::Add(g(l), g(r)),
        }
    }
}

type Expr = Fix<ExprTag>;

fn lit(n: i32) -> Expr {
    Fix::new(ExprF::Lit(n))
}

fn add(l: Expr, r: Expr) -> Expr {
    Fix::new(ExprF::Add(l, r))
}

// Build: (1 + 2) + 3
let expr = add(add(lit(1), lit(2)), lit(3));

// Evaluate via fold
let result: i32 = fold(expr, |layer| match layer {
    ExprF::Lit(n) => n,
    ExprF::Add(l, r) => l + r,
});
assert_eq!(result, 6);