Recursive Types, Fixed Points, and Folds

Lists, syntax trees, directory hierarchies, and nested documents look different, but their types make the same move: they refer to smaller values shaped like themselves. That self-reference is useful, yet a declaration such as “an expression contains expressions” hides two separate ideas. There is a one-layer shape, and there is a rule for repeating that shape until a complete value emerges.

Fixed points separate those ideas. A recursive type is a solution to an equation of the form $X \cong F(X)$, where $F$ describes one layer and $X$ marks recursive positions. A fold then supplies an interpretation for one layer and extends it uniquely across the finite structure. This is more than mathematical decoration: it removes duplicated traversal code, makes termination assumptions visible, clarifies stack failures, and lets one tree support evaluation, printing, validation, and analysis without embedding those operations in every node.

Recognize the Recursive Equation #

Start with a binary expression containing numeric literals and addition:

type Expr =
  | { kind: 'literal'; value: number }
  | { kind: 'add'; left: Expr; right: Expr };

Replace each recursive occurrence with a placeholder X. One layer becomes:

The plus sign denotes a choice between variants, not numeric addition. The product denotes a record containing both children. Substituting Expr for X recovers the original shape:

This equation identifies what is recursive and what is not. value belongs to the current layer. left and right are holes where another layer may appear. The same analysis gives a list equation $List(A) \cong 1 + (A \times List(A))$: a list is either empty, represented by the unit $1$, or one element paired with another list.

In a language with direct recursive aliases, the compiler ties this knot for us. Other languages expose the knot through an explicit wrapper or restrict where recursion may occur. The conceptual decomposition remains useful because operations usually follow exactly the one-layer cases. If a type’s recursive positions cannot be identified cleanly, traversal code will probably mix structure with unrelated state.

Recursive references should also be productive. A definition such as type Bad = Bad offers no constructor that can build a finite value and no observable layer to consume. Practical recursive data places self-reference beneath a constructor such as add, cons, some, or a record field. That guarded shape gives code one layer of progress at every step.

Tie One-Layer Shapes into a Fixed Point #

We can represent the decomposition directly in TypeScript without needing higher-kinded types:

type ExprLayer<Child> =
  | { kind: 'literal'; value: number }
  | { kind: 'add'; left: Child; right: Child };

type Expr = Readonly<{
  unfix: ExprLayer<Expr>;
}>;

const literal = (value: number): Expr => ({
  unfix: { kind: 'literal', value },
});

const add = (left: Expr, right: Expr): Expr => ({
  unfix: { kind: 'add', left, right },
});

ExprLayer<Child> knows nothing about recursion. It can contain raw expressions, evaluated numbers, printed strings, promises, IDs, or anything else at the child positions. Expr supplies itself as Child, repeating the layer. The unfix wrapper makes the isomorphism explicit: unpack one Expr to obtain ExprLayer<Expr>, or wrap that layer to construct an Expr.

In languages that distinguish iso-recursive types, these roll and unroll operations are explicit. With equi-recursive types, a compiler treats the recursive type and its unfolded form as equal during type checking. The distinction affects compiler machinery and annotations, but both describe a fixed point of the layer constructor.

The word “fixed” does not mean immutable. It means substituting the solution back into the shape produces the same type up to the relevant notion of equality. Nor does it imply one unique runtime representation. Boxed nodes, tagged memory layouts, object graphs, and compact arenas can all implement the same recursive equation.

Separating the layer is valuable even when production code retains the simpler direct union. It gives a precise vocabulary: constructors assemble one layer, recursive positions connect layers, and an operation over the whole value can be factored into recursion plus an operation over one layer.

Distinguish Least and Greatest Fixed Points #

An equation can have more than one semantic solution. Type theory separates the least fixed point, written $\mu F$, from the greatest fixed point, written $\nu F$.

The least fixed point contains values obtained by finitely applying constructors. Our expression tree is a least fixed point: every valid expression has finite depth, and repeatedly taking children eventually reaches literals. Induction is its proof principle. To establish a property for every expression, prove it for a literal and prove that an addition has the property whenever both children do.

The greatest fixed point permits potentially unending observations. A stream equation illustrates it:

A useful stream has a head now and can reveal another stream later; it need not terminate in an empty constructor. Coinduction is the corresponding proof technique: show that observations can continue while preserving a relation. Lazy iterators, reactive processes, and protocol behaviors can have this flavor even when a programming language represents them with functions rather than an infinite object already resident in memory.

Confusing the two causes API mistakes. A function that computes a complete length assumes finite input and cannot generally consume a greatest-fixed-point stream. A stream operation should instead produce observations incrementally, apply a bound such as take(100), or return another productive stream. Conversely, treating a finite tree as merely observable behavior gives up structural induction and straightforward termination arguments.

Most application data structures are intended as least fixed points, though their runtime representation may accidentally contain cycles through mutation or deserialization. A cyclic object graph is not a larger finite tree. Code must either reject cycles, assign graph semantics with a visited set, or adopt a genuinely coinductive interface.

Turn Structural Recursion into a Fold #

A conventional evaluator repeats the recursive pattern explicitly:

function evaluateDirect(expression: Expr): number {
  const layer = expression.unfix;
  switch (layer.kind) {
    case 'literal':
      return layer.value;
    case 'add':
      return evaluateDirect(layer.left) + evaluateDirect(layer.right);
  }
}

Only the final action is specific to evaluation. Unpack a node, recurse into every child, and rebuild the current layer with child results: that part is shared by any bottom-up operation. A catamorphism, usually called a fold, captures it.

First map a function over recursive positions in one layer:

function mapExprLayer<A, B>(
  layer: ExprLayer<A>,
  transform: (value: A) => B,
): ExprLayer<B> {
  switch (layer.kind) {
    case 'literal':
      return layer;
    case 'add':
      return {
        kind: 'add',
        left: transform(layer.left),
        right: transform(layer.right),
      };
  }
}

type Algebra<Result> = (layer: ExprLayer<Result>) => Result;

function foldExpr<Result>(
  algebra: Algebra<Result>,
  expression: Expr,
): Result {
  const foldedChildren = mapExprLayer(
    expression.unfix,
    (child) => foldExpr(algebra, child),
  );
  return algebra(foldedChildren);
}

An algebra has shape $F(A) \rightarrow A$. It receives one layer whose children have already become results and says how to collapse that layer. The fold supplies the traversal from $\mu F$ to $A$. This use of “algebra” means an interpreter for constructors; it does not require arithmetic.

The design enforces bottom-up access. An algebra can inspect the literal or the two child results, but it cannot accidentally recurse into the original children because they are no longer present. That constraint makes many tree analyses easier to compose and review.

Work One AST Through Several Algebras #

Build the expression $(7 + 3) + (2 + 8)$:

const expression = add(
  add(literal(7), literal(3)),
  add(literal(2), literal(8)),
);

Evaluation is now only an algebra:

const evaluate: Algebra<number> = (layer) => {
  switch (layer.kind) {
    case 'literal':
      return layer.value;
    case 'add':
      return layer.left + layer.right;
  }
};

foldExpr(evaluate, expression); // 20

Pretty-printing changes the result type and constructor meanings, not the traversal:

const print: Algebra<string> = (layer) => {
  switch (layer.kind) {
    case 'literal':
      return String(layer.value);
    case 'add':
      return `(${layer.left} + ${layer.right})`;
  }
};

foldExpr(print, expression); // "((7 + 3) + (2 + 8))"

A richer result can compute several attributes in one pass:

type Summary = Readonly<{
  value: number;
  depth: number;
  literals: number;
}>;

const summarize: Algebra<Summary> = (layer) => {
  switch (layer.kind) {
    case 'literal':
      return { value: layer.value, depth: 1, literals: 1 };
    case 'add':
      return {
        value: layer.left.value + layer.right.value,
        depth: 1 + Math.max(layer.left.depth, layer.right.depth),
        literals: layer.left.literals + layer.right.literals,
      };
  }
};

foldExpr(summarize, expression);
// { value: 20, depth: 3, literals: 4 }

The worked example reveals the abstraction’s payoff. Adding multiplication requires updating ExprLayer, its mapper, and each algebra; TypeScript’s exhaustive switches identify every affected interpretation. Adding a new analysis requires only another algebra. Structural recursion remains centralized.

Some tasks do not fit a plain catamorphism. Constant folding must return a transformed tree and may be a fold, but reporting each node’s source path needs inherited top-down context. Comparing siblings before recursively deciding which one to visit may require explicit control. Sharing repeated subtrees may call for memoization. A fold is a precise tool for uniform bottom-up consumption, not a mandate to force every traversal into one signature.

Make Deep Folds Stack-Safe #

The recursive foldExpr consumes one call-stack frame per tree level. A balanced tree with many nodes has logarithmic depth, but a parser, generated document, or adversarial payload can produce a chain deep enough to exceed the runtime’s stack. Tail-call optimization does not rescue the function: after folding a child, it still must combine results, and common JavaScript runtimes do not guarantee proper tail calls in this situation.

Use an explicit postorder stack when depth is untrusted:

type Work =
  | { state: 'visit'; expression: Expr }
  | { state: 'combine'; layer: ExprLayer<Expr> };

function foldExprIterative<Result>(
  algebra: Algebra<Result>,
  root: Expr,
): Result {
  const work: Work[] = [{ state: 'visit', expression: root }];
  const results: Result[] = [];

  while (work.length > 0) {
    const item = work.pop()!;

    if (item.state === 'visit') {
      const layer = item.expression.unfix;
      work.push({ state: 'combine', layer });
      if (layer.kind === 'add') {
        work.push({ state: 'visit', expression: layer.right });
        work.push({ state: 'visit', expression: layer.left });
      }
      continue;
    }

    if (item.layer.kind === 'literal') {
      results.push(algebra(item.layer));
      continue;
    }

    const right = results.pop();
    const left = results.pop();
    if (left === undefined || right === undefined) {
      throw new Error('Malformed traversal state');
    }
    results.push(algebra({ kind: 'add', left, right }));
  }

  if (results.length !== 1) throw new Error('Malformed expression');
  return results[0]!;
}

Children are pushed right first so the left child is visited first; results are then popped in reverse completion order. Both stacks use $O(depth)$ auxiliary space for a tree, as the call stack did, but the capacity is now heap-backed and controllable. The algorithm remains $O(nodes)$.

For very large values, impose node and depth limits during decoding rather than relying only on a stack-safe consumer. Stack safety prevents one failure mode; it does not make unbounded memory or CPU acceptable. A streaming parser or arena representation may be a better design when complete materialization is unnecessary.

Know Where the Abstraction Breaks #

Recursive types invite several subtle failures.

Accidental cycles turn a terminating fold into an infinite loop. Immutable constructors help but do not protect data assembled through unsafe casts or mutable object graphs. Reject repeated object identities during boundary decoding when tree semantics are required.

Non-positive recursion places the recursive type to the left of a function arrow, as in a shape containing (self: X) => never. Such definitions undermine the monotone shape intuition behind ordinary least fixed points and can threaten soundness in expressive type systems. Application-level recursive records and variants should keep recursive occurrences in data-producing positions unless the language’s rules explicitly support more.

Hidden effects make fold order observable. If an algebra writes logs, mutates shared state, or performs asynchronous work, left-to-right versus parallel traversal matters. Encode effects in the result or document the sequencing contract instead of assuming a mathematically pure fold grants operational freedom.

DAGs treated as trees recompute a shared subtree once per incoming edge. Memoize by stable node identity when sharing is intentional, but then define whether results depend only on the node or also on its path. A visited set used for cycle detection is not automatically a result cache.

Over-generalization can make a simple domain unreadable. A reusable foldExpr is worthwhile when a stable shape has several bottom-up consumers. A fully generic fixed-point encoding with simulated higher-kinded types may add more type machinery than a small codebase gains. Preserve the one-layer insight even if the public API remains a direct recursive union.

Verify Constructors, Folds, and Depth Behavior #

Tests should establish both each algebra’s meaning and the traversal’s structural behavior. Begin with one constructor at a time: a literal, an addition of two literals, a balanced tree, and a left-skewed tree. For the worked expression, assert evaluation 20, rendering ((7 + 3) + (2 + 8)), depth 3, and literal count 4.

Then compare implementations. Generate bounded random expression trees and assert that evaluateDirect, foldExpr(evaluate, tree), and foldExprIterative(evaluate, tree) agree. This differential test is powerful because the implementations organize recursion differently. Also test negative numbers, NaN, and infinities if the domain permits them; otherwise make constructors reject those values and test rejection.

Exercise the operational boundary with a deliberately deep skewed tree. The iterative fold should complete within configured node limits even where the recursive fold is expected to exceed the environment’s safe depth. Do not assert one universal failure depth, because stack limits vary. Verify instead that production entry points choose the iterative path or reject excessive depth before recursive processing.

If expressions arrive from JSON, test cycle policy separately from schema shape, enforce node/depth budgets, and return stable validation errors. Instrument rejected depth, node counts, and fold duration without logging entire trees. A sudden shift toward deep inputs can indicate a producer regression or deliberate resource attack.

Finally, use exhaustive switches and a never assertion where the language configuration requires it, so adding a constructor exposes incomplete algebras at compile time. The fixed-point view earns its keep when evolution is local and omissions are visible.

Recursive data is not mysterious self-reference. It is a repeatable one-layer shape tied into a least or greatest fixed point. For finite ASTs and trees, structural induction justifies a fold; an algebra explains what each constructor means after its children have been processed. That separation supports many interpretations, while explicit work stacks and input limits make the same reasoning operationally safe. Use the mathematics to expose assumptions, then choose the simplest encoding that keeps those assumptions testable in the codebase at hand.