Module fix 

Fixed-point types and recursion schemes

This module provides the building blocks for recursion schemes in Rust:

• TypeApp: Higher-kinded type encoding
• Functor: Functor on one type parameter
• Fix: Least fixed point (μF)
• fold: Catamorphism / F-algebra eliminator

Example: Linked List

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

// Base functor for List<A>: ListF<A, X> = Nil | Cons(A, X)
enum ListF<A, X> {
    Nil,
    Cons(A, X),
}

// Type-level tag for ListF<A, _>
struct ListTag<A>(std::marker::PhantomData<A>);

impl<A> TypeApp for ListTag<A> {
    type Applied<X> = ListF<A, X>;
}

impl<A: Clone> Functor for ListTag<A> {
    fn fmap<X, Y, G>(fx: ListF<A, X>, mut g: G) -> ListF<A, Y>
    where
        G: FnMut(X) -> Y,
    {
        match fx {
            ListF::Nil => ListF::Nil,
            ListF::Cons(a, x) => ListF::Cons(a.clone(), g(x)),
        }
    }
}

// List<A> is the fixed point of ListF<A, _>
type List<A> = Fix<ListTag<A>>;

// Smart constructors
fn nil<A: Clone>() -> List<A> {
    Fix::new(ListF::Nil)
}

fn cons<A: Clone>(head: A, tail: List<A>) -> List<A> {
    Fix::new(ListF::Cons(head, tail))
}

// Build a list: [1, 2, 3]
let list = cons(1, cons(2, cons(3, nil())));

// Compute length via fold
let length: usize = fold(list, |layer| match layer {
    ListF::Nil => 0,
    ListF::Cons(_, n) => n + 1,
});
assert_eq!(length, 3);

Structs

Fix

The least fixed point (μF) of a functor F.

Traits

Functor

A functor for type constructors.

TypeApp

A type constructor encoding via associated types.

Functions

fold

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