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).
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.
Catamorphism as a composable Getter, driven by Plated[S]. The algebra sees the original node S (paramorphism-flavored) plus its already-folded children. Stack-safe; folds child results in place (see the private foldInPlace engine) so it allocates one array per node, not two.
Catamorphism as a composable Getter, driven by Plated[S]. The algebra sees the original node S (paramorphism-flavored) plus its already-folded children. Stack-safe; 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. The typed pattern-functor path is where a pure F[A] => A algebra is fully expressive, because F's constructors carry what PSVec erases.
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.