Recursion schemes as composable optics, built on the core optic surface.
cata is a Getter[S, A] driven by Plated[S] — the structural fold, generalising Plated.transform from S => S to S => A.
ana is a Review[S, Seed] — the unfold (build S from a seed), taking a Coalg.
hylo is a fusedGetter[Seed, A] — refold with no intermediate S built.
Because they produce core optic types, they compose with the rest of the optic algebra: someLens.andThen(cata(alg)), and the materializing ana(…).cross(cata(…)) (via the core Optic.cross combinator) — the latter equal to hylo on the same computation (the hylo law).
Two usage modes. Run the optic directly (cata(alg).get(tree), ana(coalg).reverseGet(seed), hylo(expand, alg).get(seed)) — or hand it to capability-consuming code: the concrete optic types implement the capability traits, so a cata / hylo result satisfies CanGet[S, A] (and CanFold[S, A]) and an ana result satisfies CanReverseGet[S, Seed], meaning a consuming signature like
accepts a catamorphism without ever naming Getter.
The fold schemes (cata / hylo) take an algebra (N, PSVec[R]) => R — a node plus its already-folded children (paramorphism-flavored). The build scheme (ana) takes a Coalg, the canonical anamorphism shape: a seed yields its child seeds together with how to assemble the node. Both run on one stack-safe engine: a < 512-deep on-stack fast path (no heap frames) that falls back, per deep subtree, to a heap ArrayDeque machine — the same hybrid as Plated.transform. Shallow trees pay no frame allocation; arbitrarily deep ones stay stack-safe.
Closure-carrying coalgebra (the anamorphism input): a seed yields its child seeds plus a combiner from the built/folded child results. A leaf is (PSVec.empty, _ => value). The combiner is handed a PSVec[R] of the same length and order as the child-seed vector — index it consistently with that arity (reading kids(1) of a 1-element vector throws IndexOutOfBounds; ignoring kids(2) of a 3-element one silently drops that subtree). A builder that captures nothing (e.g. ks => Node(ks(0), ks(1))) is a singleton in Scala 3, so the per-node cost of this bundled shape is just the tuple.
Closure-carrying coalgebra (the anamorphism input): a seed yields its child seeds plus a combiner from the built/folded child results. A leaf is (PSVec.empty, _ => value). The combiner is handed a PSVec[R] of the same length and order as the child-seed vector — index it consistently with that arity (reading kids(1) of a 1-element vector throws IndexOutOfBounds; ignoring kids(2) of a 3-element one silently drops that subtree). A builder that captures nothing (e.g. ks => Node(ks(0), ks(1))) is a singleton in Scala 3, so the per-node cost of this bundled shape is just the tuple.
Anamorphism as a Review (reverse-construction optic): a stack-safe unfold Seed => S driven by a Coalg. Materializing — the built S is O(nodes).
Anamorphism as a Review (reverse-construction optic): a stack-safe unfold Seed => S driven by a Coalg. Materializing — the built S is O(nodes).
Stack-safety contract: below the 512-frame on-stack limit the unfold recurses directly on the JVM stack; past it, each deep subtree is handed to a heap ArrayDeque machine — so any ''terminating'' coalgebra builds without StackOverflowError, at any depth, and a non-terminating one fails by exhausting the heap (OutOfMemoryError), not the stack.
Catamorphism as a composable Getter, driven by Plated[S]. The algebra sees the original node S (paramorphism-flavored) plus its already-folded children.
Catamorphism as a composable Getter, driven by Plated[S]. The algebra sees the original node S (paramorphism-flavored) plus its already-folded children.
Stack-safety contract: below the 512-frame on-stack limit the fold recurses directly on the JVM stack (no heap frames); past it, each deep subtree is handed to a heap ArrayDeque machine — so any finite tree folds without StackOverflowError, at any depth, and a Plated whose children never bottom out fails by exhausting the heap (OutOfMemoryError), not the stack. Folds child results in place (see the private foldInPlace engine) so it allocates one array per node, not two.
Catamorphism from a build-only optic citizen: a pure algebra PSVec[A] => A carried as an dev.constructive.eo.optics.Unfold, so an algebra built by optic composition (review.andThen(unfold), unfold.andThen(review)) drops straight into the fold engine.
Catamorphism from a build-only optic citizen: a pure algebra PSVec[A] => A carried as an dev.constructive.eo.optics.Unfold, so an algebra built by optic composition (review.andThen(unfold), unfold.andThen(review)) drops straight into the fold engine.
Note the honesty limit of the untyped path: a PSVec layer is node-blind, so a pure PSVec[A] => A can express only constructor-independent folds (size, child counts, …) — eval-style algebras need the para-flavored (S, PSVec[A]) => A overload above. A typed pattern-functor path — where a pure F[A] => A algebra would be fully expressive, because F's constructors carry what PSVec erases — is ''planned'' but not part of this artifact yet: there is no cataF entry point to look for.
Hylomorphism — the fused refold Seed => A, building no intermediate S: expand unfolds seeds and alg folds to A in one post-order pass. Returned as a Getter[Seed, A] so it composes further. Equal to ana(…).cross(cata(alg)) on the same computation (the hylo law), but without materializing the structure.
Hylomorphism — the fused refold Seed => A, building no intermediate S: expand unfolds seeds and alg folds to A in one post-order pass. Returned as a Getter[Seed, A] so it composes further. Equal to ana(…).cross(cata(alg)) on the same computation (the hylo law), but without materializing the structure.
Stack-safety contract (same as cata / ana): on-stack recursion below the 512-frame limit, then a heap ArrayDeque machine per deep subtree — safe for any ''terminating'' expand at any depth; a non-terminating expand fails by exhausting the heap (OutOfMemoryError), not by StackOverflowError.