dev.constructive.eo.schemes

Typed recursion schemes as composable optics, over a user-supplied pattern functor F[_] (+ Traverse[F]) and the Basis (Project/Embed) correspondence to the recursive type S.

==The thesis==

A recursion scheme is an dev.constructive.eo.optics.Optic over the dev.constructive.eo.data.Direct carrier whose existential X is the index of the recursion — what the scheme retains — and the (co)free (co)monads are the universal indices:

scheme	X	index
cata	Nothing	the forgetful (trivial) fold
zygo	F[(B, A)]	store comonad over an auxiliary carrier B
para	F[(S, A)]	the store-comonad complement (subterms)
histo	zoo.Attr = νX. A × F[X]	the cofree comonad (course-of-value fold)
ana	S	the materialising unfold
cozygo	Either[B, A]	g-apo residual over an auxiliary coalgebra
apo	Either[S, A]	the Prism residual (graft, build-side)
futu	zoo.Coattr = μX. A + F[X]	the free monad (multi-layer unfold)

para/histo refine cata's index up the comonad tower; apo/futu refine ana's up the monad tower. (para's existential is the writable-Lens complement — get-put holds definitionally, put-get only under algebra-coherence, so the lawful writable put is a scoped follow-up.)

The towers also have an auxiliary rung between the trivial and store/prism indices: zygo (X = F[(B, A)], the store comonad over an arbitrary carrier B — para is zygo at B = S) and its mutual-recursion generalisation mutu (X = F[(A, B)]), with build-side duals cozygo (X = Either[B, A], g-apo) and comutu (X = Either[A, B]).

Orthogonal to both towers is the natural-transformation axis — prepro / postpro keep the trivial index (cata/ana-shaped) and instead pre/post-compose the layer optic (fLayer) with an accumulating η : F ~> F, so a node at depth k is transformed k times (O(n · depth); η = id recovers cata/ana).

==hylo is the fusion, not a primitive — and meta is the honest non-fusion==

ana is a build (Review-shaped) and cata a node-blind fold (Getter-shaped); the build⇄read seam ana.cross(cata) (definitionally ana.reverse.andThen(cata)) fuses — the citizens keep their coalg/alg alive — into zoo.Hylo, building no intermediate S. The FusionSpec pins the hylo law and witnesses the deforestation (the fused refold never calls project/embed).

The fold→unfold seam cata.meta(ana) is the direction-dual (meta, the metamorphism), and it cannot fuse: fold and unfold range over different functors, so the neck value is materialised (the zoo.Meta existential is X = A, not Nothing). The 2×2 the two seams complete — refold vs metamorphism × trivial vs universal index — is zoo.Hylo / zoo.Meta / zoo.Chrono / zoo.MetaChrono; the quadrant's diagonals are zoo.Dyna (ana.cross(histo)) and zoo.Codyna (futu.cross(cata)). zoo.Elgot / zoo.Coelgot are the short-circuit / seed-reading refold variants.

==Shape==

Every scheme is a final class in zoo carrying its run/build function (the construction and machine-wiring live in each class's companion); this object is the user-facing factory listing — one-line delegations — plus fLayer. All schemes run on one stack-safe engine (Machines.foldLayered): a < 512-deep on-stack fast path falling back per deep subtree to a heap ArrayDeque machine — stack-safe to 10⁶, tested.