Struct Fix 

pub struct Fix<F: TypeApp>(/* private fields */);

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

Fix<F> satisfies the isomorphism:

Fix<F> ≅ F(Fix<F>)

Why Fix<F> satisfies X ≅ F(X) (for a Haskeller)

We freely mix real Haskell syntax with informal type-equation expansions to show what the types mean. Some lines below are explanatory and are not meant to compile literally.

Start with an ordinary recursive datatype:

data List a = Nil | Cons a (List a)

Read this as a sum/product equation over values:

List a ≅ 1 + (a × List a)

where:

• 1 is the singleton set (the Nil case),
• + is disjoint sum (choice of constructor),
• × is product (constructor arguments).

At this point we are no longer doing category theory — we are solving a type equation. A recursive datatype is precisely one whose values are defined in terms of smaller values of the same type. Writing the constructors this way makes that explicit: we are looking for a type X such that X appears on both sides of its own definition. That is exactly what a fixed point is.

Now factor out the recursive position by naming the shape that still has a hole.

In Haskell syntax:

data ListF a x = Nil | Cons a x

Schematic (equational) form of the same declaration:

ListF a X = 1 + (a × X)

This separates the shape of the structure from the recursion itself.

Substituting the original type back into the hole gives:

List a ≅ ListF a (List a)

which is exactly the fixed-point equation:

X ≅ F(X)

with X = List a and F = ListF a.

We write ≅ (isomorphism), not =, because recursive types are represented by wrappers, not by definitional equality. In Haskell this is explicit:

newtype Fix f = Fix (f (Fix f))

unFix :: Fix f -> f (Fix f)

In Rust, direct self-recursion is not representable without indirection, so Fix<F> stores F::Applied<Fix<F>> inside a Box. This establishes the same isomorphism by construction rather than by definitional equality.

Unrolling makes the correspondence concrete by showing what “one layer” means.

Specialize Fix to lists:

type List a = Fix (ListF a)

Now compute unFix at that specialization:

unFix :: List a -> ListF a (List a)
      :: Fix (ListF a) -> ListF a (Fix (ListF a))

-- meta-level expansion of the constructors (not valid Haskell syntax)
      :: Fix (ListF a) -> (Nil | Cons a (Fix (ListF a)))

That final line is not Haskell code — it is the semantic expansion of the datatype. It shows that one step of unrolling a list yields exactly one constructor layer: either Nil, or Cons a paired with a recursive tail.

In Rust, the same unrolling exists with different names and explicit indirection:

Fix<F>::out : Fix<F> -> F::Applied<Fix<F>>

For F = ListTag<A> where F::Applied<X> = ListF<A, X>:

Fix<ListTag<A>>::out : Fix<ListTag<A>> -> ListF<A, Fix<ListTag<A>>>

The Box is purely representational — it makes the recursive type finite in memory — and does not change the mathematical meaning of the unrolling.

Why “least” fixed point?

The equation X = F(X) can have multiple solutions, including infinite, non-well-founded ones. The least fixed point μF is the smallest solution closed under the constructors — the inductive (finite) values.

In domain-theoretic terms, μF is the join of an ascending chain:

μF = ⊔{Fⁿ(⊥) | n ∈ ℕ}

For a concrete intuition, let:

ExprF<X> = Lit(i32) | Add(X, X)

Then:

• E₀ = ⊥ (empty)
• E₁ = Lit(n)
• E₂ = Lit(n) | Add(Lit, Lit)
• E₃ = Lit(n) | Add(E₂, E₂)
• …
• μExprF = ⊔Eₙ = all finite expression trees

Each stage adds one more layer of depth. The fixed point is the union of all finite stages — exactly the recursive datatype we intend to model.

Send / Sync

Fix<F> is Send iff F::Applied<Fix<F>> is Send. Fix<F> is Sync iff F::Applied<Fix<F>> is Sync.

Example

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

// Natural numbers: Nat = Zero | Succ(Nat)
enum NatF<X> {
    Zero,
    Succ(X),
}

struct NatTag;

impl TypeApp for NatTag {
    type Applied<X> = NatF<X>;
}

type Nat = Fix<NatTag>;

// Smart constructors hide the Fix::new calls
fn zero() -> Nat { Fix::new(NatF::Zero) }
fn succ(n: Nat) -> Nat { Fix::new(NatF::Succ(n)) }

let two = succ(succ(zero()));

Implementations

impl<F: TypeApp> Fix<F>

pub fn new(node: F::Applied<Fix<F>>) -> Self

Construct a Fix from one layer of the functor.

This is the “in” morphism: F(Fix F) → Fix F

pub fn out(self) -> F::Applied<Fix<F>>

Unwrap one layer of the functor, consuming the Fix.

This is the “out” morphism: Fix F → F(Fix F)

pub fn as_out(&self) -> &F::Applied<Fix<F>>

Borrow one layer of the functor.

Trait Implementations

impl<F> Clone for Fix<F>

where F: TypeApp, F::Applied<Fix<F>>: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F> Debug for Fix<F>

where F: TypeApp, F::Applied<Fix<F>>: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F> PartialEq for Fix<F>

where F: TypeApp, F::Applied<Fix<F>>: PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F> Eq for Fix<F>

where F: TypeApp, F::Applied<Fix<F>>: Eq,