Paramorphism¶
A structural recursion scheme whose combining step receives both each original recursive subobject and the result recursively computed from it.
Core Idea¶
A paramorphism folds an inductive value but refuses to discard each child when its folded result becomes available. The combining step receives both: for a list, the original remaining tail and the recursively computed result for that tail; for a natural number, the predecessor and its recursive result.
This retained context is exactly the difference from a catamorphism. It supports functions such as factorial and suffix-sensitive computations while preserving structural descent. An apomorphism is the categorical dual on the unfolding side, where construction can emit already formed substructures.
Scope of Application¶
- Functional programming. Recursion-scheme libraries express context-retaining folds.
- Formal methods. Structural interfaces support equational reasoning and termination.
- Compiler transformations. Recursive syntax processing can retain original subtrees beside analyses.
- Category theory. Initial-algebra folds are extended and related to their duals.
Clarity¶
Specify the base functor or constructors, result type, base case, original child passed at each step, recursive result, combining algebra, and structural termination argument. Show why a catamorphism is insufficient rather than using paramorphism as a generic recursion label. Inclusion test: A recursion is paramorphic when each structural step receives the original recursive child together with that child's recursively computed result. Exclusion test: A catamorphism is excluded when the step sees only recursive results and constructor payload. Nearest boundary: A general recursive function that can inspect its entire input is nearby but lacks the disciplined one-layer structural interface. Exit condition: The identity exits when the original child is unavailable, recursion is not structurally decreasing, or unfolding rather than folding is the governing direction. Common misclassifications: It is not an ordinary catamorphism whose step sees only folded children. It is not arbitrary unrestricted recursion over the whole input. It is not an apomorphism, which is its unfolding dual. It is not parameter passing in the everyday programming sense merely because the names sound similar. Nearest named distinctions: Catamorphism: Passes recursive results but not the original recursive children. Apomorphism: Unfolds and may reuse prebuilt output substructures. Primitive recursion: Is closely related on naturals but is not the general datatype-level name in every formulation. General recursion: Can inspect arbitrary inputs and need not be structurally decreasing.
Manages Complexity¶
The scheme packages a common recursive dependency into a reusable typed interface. It removes explicit recursive control while exposing just enough original structure. The extra access can retain large subtrees or weaken fusion properties, so its cost and semantic necessity should remain visible.
Abstract Reasoning¶
- Describe the inductive carrier and constructors.
- Identify the result type and nullary base result.
- For each recursive field, compute the result structurally.
- Pass both original child and computed result to the step algebra.
- Verify that recursive calls strictly descend through constructors.
- Compare the definition with a catamorphism and isolate the retained-context need.
- Use duality with apomorphism only after fold and unfold directions are fixed.
Knowledge Transfer¶
The scheme transfers among lists, trees, natural numbers, and other initial-algebra data when original children and recursive results can be paired. It stops at nonstructural recursion without a suitable inductive carrier. The cargo is context-retaining fold structure.
Neighborhood in Abstraction Space¶
Paramorphism sits in a moderately populated region (48th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Recursive Construction Schemes (8 abstractions)
Nearest neighbors
- Programming Fold — 0.89
- Bijective proof — 0.87
- Join of Categories — 0.86
- Cyclic homology — 0.86
- K-theory — 0.86
Computed from structural-signature embeddings · 2026-10-08