betaFeedback

WorksComputer Science

Datatypes In, Zippers Out!

Abstract

A zipper represents a focused position in an algebraic data structure together with the context needed to reconstruct the whole. Datatype derivatives determine one-hole context types, but do not by themselves choose a zipper's concrete representation or specify navigation costs and demands. We present Kamot, a tool that converts regular algebraic datatype declarations in a restricted Haskell fragment into zipper implementations with operational contracts. Navigation, replacement, and reconstruction are proved correct against a reference traversal. Kamot supports mutual recursion and regular containers inside containers. A compositional analysis derives sound bounds on transitions and constructor demands for certified traversal directions. These bounds are affine in trail depth (the number of saved frames) and guarantee termination of each move on productive, potentially infinite inputs. For inhabited families the analysis is complete: when no move certificate is emitted, no bound depending only on trail depth exists, and some productive input makes a move diverge. We prove that the generated code preserves results and the reference order of constructor matches, including finite prefixes of divergent searches. Lean 4 verifies simulation, bounds, and completeness for finite values of single self-recursive datatypes, in both directions. On 19 datatype models and 81 generated families, every generated module passes Haskell type checking, and independent checkers validate certificates, traces, and bounds. In a prefetching workload, starting only searches whose bounds fit a budget answers every local query and avoids discarded source evaluations on long returns, but conservative bounds can lose answers that fuelled search delivers.

CCS Concepts: • Software and its engineering → Compilers; • Theory of computation → Program verification.

Introduction

A zipper represents a position in an algebraic data structure together with its surrounding context [15]. It lets a program inspect a value, replace it, and continue navigating without searching again from the root. The surrounding structure is retained, so the program can reconstruct the updated whole while older versions remain available. These operations are useful when an editor moves through a syntax tree, or a consumer pauses and resumes a traversal of lazily produced data.

Consider a rose tree, in which each node holds a label and a list of children:

data Tree a = Node a [Tree a]

Figure 1 shows a zipper focused on the label G of a ten-node tree (node labels are set in sans serif). It keeps three parts. The path has one crumb per ancestor: the ancestor’s label and the siblings on either side of the child that was entered, with a hole in its place. The crumb nearest the focus, C’s, sits at the accessible end of the path. Returning to C uses that crumb directly, filling its hole with the rebuilt subtree at G. Within a crumb, the nearest earlier sibling and the nearest later sibling are likewise the ones exposed. The children component is G’s child list, and the focus is its label. Together with the path they reconstruct the tree.

Datatype derivatives compute one-hole context types [1, 22]; the crumb above is a value of one. McBride’s dissection goes further, deriving executable navigation and tail-recursive folds by distinguishing processed results from pending inputs [23]. We build on these constructions to derive operational contracts: bounds on the work done and the source constructors forced between one focused label (an observation) and the next.

Such guarantees matter even though the zipper reaches the nearest crumb in one step. In Figure 1, a forward move from G inspects the first cell of its child list and the node it holds, then focuses H, leaving the other children unforced. A forward move from I must instead return through G and C before it reaches D, and in general may cross several empty child lists. On an infinite input, one search can fail to return even though every constructor it requests is produced in finite time. A client deciding whether to start a search needs a bound on that search, which the type of the saved state does not provide.

A rose tree and its zipper focused on the label G

Figure 1. A rose tree and its zipper focused on the label G: path, children, focus. The path holds one crumb per ancestor, drawn root first; a crumb keeps the ancestor’s label and its other children around a hole (dashed). The path’s pointed end, accessed first, exposes C’s crumb. The bounds in the text count frames. The path has five: A’s node and the list cells holding B and C, then C’s node and the cell holding G.

Whether a move is cheap depends on the datatype. In the rose tree every node starts with its label, so when next enters a nonempty child list, the first node it meets yields a label at once. Seeing this requires looking through both constructors, since a list cell has no label of its own. Now add a constructor Silent [Tree a]: a node with children but no label. A search that enters a chain of silent nodes keeps descending without finding a label, and on an infinite chain it never returns. The same construction gives both datatypes zippers, but only the first guarantees a bounded next.

Our approach derives the traversal and its analysis from the same ordered datatype description. Differentiation produces local contexts for recursive children, stored as records called frames; a finite stack of frames, the trail, keeps the nearest one accessible. A move is a search that runs generated clauses, one per transition (entering a constructor, resuming after a field, or returning through a frame). It either yields an element or returns without one. The analysis composes their work and demand summaries across mutually recursive types and container fields, then along the saved trail. A search that must yield before returning to a saved frame can be bounded from its current position alone; one that may return also depends on the saved frames. The analysis guarantees the following.

For every direction (forward or backward) with an emitted move certificate, a move from a cursor with hh saved frames reaches its next element or the boundary within work and constructor-demand bounds affine in hh, provided each demanded constructor is produced in finite time (Theorem 8.2).

For the rose tree, the bounds are 4+3h4+3h transitions and 2+2h2+2h constructor demands; hh counts frames, for list cells as well as tree nodes, so it grows with the number of earlier siblings on the path as well as with depth; h=5h = 5 at G in Figure 1. With Silent, the analysis emits no move certificate, and no bound depending only on hh exists (Theorem 8.4). The guarantee applies to each observation, without requiring the input to be finite or its size to be known. It does not make depth-first traversal fair: an infinite subtree can still keep its later siblings from ever being visited.

A client can compare a move’s bounds with its work and demand budgets before forcing any source constructor: it can start the move when the bounds fit, or defer it when an edit may soon cancel the query. Resumable execution splits a longer or uncertified search into slices of bounded length. The bounds count structural steps; evaluating one source thunk may still take arbitrary time, and a conservative bound can defer a search that would have been cheap.

We make three contributions:

  • Compositional contracts. Per-type summaries of search work and demand compose across mutually recursive types and regular containers to certify the work, source demand, and conditional termination of each move (Theorem 8.2). Charging each saved frame its own outcome sharpens the bound (Theorem 8.3). For inhabited families (every sort occurs in a finite value and has a finite value containing an element) the move analysis is complete for the generated traversal: it emits no move certificate exactly when no bound depending only on hh exists (Theorem 8.4).

  • A compilation account. Ordered derivative records and indexed trails represent finite paths, including paths within infinite values. Generated operations preserve the reference traversal’s result and ordered demand trace, including every finite prefix of a divergent search (Theorems 4.2, J.1, 7.1, and 7.2). The same construction supports a resumable backend for eager folds (§ 9).

  • An implementation and evaluation. We implement this approach in Kamot, which emits specialised Haskell and machine-readable contracts. Independent tools check the certificates and execution traces. We evaluate certificate precision, admission decisions, compiler scaling, and runtime costs against handwritten and generic implementations (§ 10). In the measured family workloads, generated cursors match the handwritten indexed stack’s allocation, with overlapping timing ranges.

The generated cursor interface

Kamot compiles the rose-tree declaration of § 1 into a Haskell module. The cursor constructors stay private. Specialised to a rose tree, its main operations are

openFirst, openLast :: Tree a -> Maybe (Zipper a Tree)
next, previous     :: Zipper a Tree -> Maybe (Zipper a Tree)
focus              :: Zipper a Tree -> a
replace            :: a -> Zipper a Tree -> Zipper a Tree
closeTree          :: Zipper a Tree -> Tree a

openFirst and openLast focus the first and last label in traversal order: depth first, following constructor field order, so each label precedes its children. next and previous move one label along that order and return Nothing past either end. focus and replace read and overwrite the focused label and touch only the cursor record. closeTree rebuilds the whole tree. A client can therefore stream the labels, pausing, resuming, or editing between calls, without restarting from the root. On the tree of Figure 1, openFirst focuses A, and repeated next visits B, E, F, C, G, H, J, I, D.

Each crumb is a value of a datatype derivative. Write XX for labels, TT for trees, and List TList\ T for lists of trees. Treating the list informally as a field type (§ 3 makes this precise by lowering), one crumb of the path of a rose tree has type

X×List T□List TX \times List\ T \mathbin{\Box} List\ T

which keeps the fields in order: the label, the earlier siblings, the hole □\Box where the path continues, and the later siblings. The terminal context has type 1□List T1 \mathbin{\Box} List\ T, a hole for the focused label followed by its children, and the focus adds an XX. Differentiation (written D\mathcal{D}; § 3) computes these types at compile time; their values carry saved fields at run time [23]. Generated code stores these contexts, passes them between operations, and pattern matches on them to resume traversal.

Kamot lowers the child list to an auxiliary datatype. Each crumb becomes several frames (lowered records): one for the label, one for each earlier sibling, and one for the later siblings (§ 4.1). The most recently crossed frame is kept at the accessible end, because it is the one the next return needs; § 4 derives this layout.

Because the interface focuses labels rather than subtrees, next searches from the terminal context until it finds another label or reaches the boundary. Removing the nearest frame takes constant structural work (§ 7), and the trail stays finite even when saved subtrees are infinite; reaching the next label may take longer, and § 8 bounds that search across the tree and list types.

Compiling ordered datatype descriptions

Kamot’s intermediate representation (IR) describes a family of mm mutually recursive datatypes, called sorts. Each sort is a finite sum of finite ordered products:

Φi(X,Y)=∑c∈Ci∏ℓ=0ac−1Ec,ℓ,Ec,ℓ::=X∣Yj∣V.\Phi_i(X,Y) = \sum_{c \in C_i} \prod_{\ell=0}^{a_c-1} E_{c,\ell}, \qquad E_{c,\ell} ::= X \mid Y_j \mid V .

Here CiC_i is the set of constructors of sort ii and aca_c is the number of fields of constructor cc. The element parameter is XX; Y=(Y1,…,Ym)Y = (Y_1, \ldots, Y_m) names recursive child sorts, and VV ranges over field types independent of XX and all YjY_j. A summand’s degree in YY is its number of recursive fields, and any degree is allowed. Constructor names distinguish summands and field indices distinguish factors. Products are ordered, so for bodies F1,F2F_1, F_2 the products F1×F2F_1 \times F_2 and F2×F1F_2 \times F_1 are distinct, and the syntax is not quotiented by type isomorphism. An empty product gives a nullary constructor and an empty sum an empty type. When m=1m = 1, every recursive field refers to the datatype itself, as in a cons list; we call such datatypes one-sort.

The declaration frontend accepts one shared parameter aa and the field grammar

τ::=a∣Ti a∣V∣[τ]∣Maybe τ∣Either τ τ∣U τ.\tau::= a \mid T_i\ a \mid V \mid[\tau] \mid Maybe\ \tau\mid Either\ \tau\ \tau\mid U\ \tau.

Each UU is a user-declared unary, strictly positive regular container. Regular recursion reuses its parameter unchanged. Strict positivity here permits recursive occurrences through the admitted sums, products, and containers, and excludes function fields.

Lowering instantiates each container body at the container’s argument. A declaration is accepted only when the closure of these instantiations is finite and every recursive family occurrence stays at the shared parameter. Container references back to root family types would change their arguments and are rejected; so are unreachable container declarations.

Lowering replaces every accepted container application by a specialised auxiliary sort and its ordered regular body (Figure 2). Appendix § 25.§ 2 proves that lowering preserves traversal order and demand up to renaming. The generated module defines its own lowered types and provides no conversion from Prelude values; conversion work and its demands lie outside every contract.

Lowering the rose tree

Figure 2. Lowering the rose tree. The list field becomes the fresh sort List0, whose constructors keep the order of [] and (:), with List0 itself as the tail.

We write μ\mu for the least fixed point, allowing only finite unfoldings of the bound recursion, and ν\nu for the greatest fixed point, which also admits infinite unfoldings. The rules below are for one sort, T=μY.Φ(X,Y)T = \mu Y.\Phi(X,Y) with constructor set CC; § 4.1 supplies their family indices and § 8 their reading at ν\nu.

We write DD for the standard derivative [1, 22]. Its rules on a constructor body are:

DXX=1,DXY=0,DXV=0,D_X X = 1,\qquad D_X Y = 0,\qquad D_X V = 0,
DX(F1+F2)=DXF1+DXF2,D_X(F_1 + F_2) = D_X F_1 + D_X F_2,
DX(F1×F2)=DXF1×F2+F1×DXF2.D_X(F_1 \times F_2) = D_X F_1 \times F_2 + F_1 \times D_X F_2.

Here 00 is the empty type and 11 the unit type. The rules for DYD_Y swap the roles of XX and YY. Differentiating in each variable gives

K=(DYΦ)[T/Y],B=(DXΦ)[T/Y].K = (D_Y\Phi)[T/Y],\qquad B = (D_X\Phi)[T/Y].

A KK stores the context around one recursive child; a BB stores the context around one direct element. As in dissection [23], the product rule keeps every factor on its own side of the hole, so each summand splits into the fields before the hole and those after it:

K=∑c∈C∑ℓ:Ec,ℓ=YLc,ℓ□Rc,ℓ,B=∑c∈C∑ℓ:Ec,ℓ=XLc,ℓ□Rc,ℓ,K = \sum_{c\in C}\sum_{\ell:E_{c,\ell}=Y} L_{c,\ell}\Box R_{c,\ell},\qquad B = \sum_{c\in C}\sum_{\ell:E_{c,\ell}=X} L_{c,\ell}\Box R_{c,\ell},
Lc,ℓ=∏ℓ′<ℓEc,ℓ′[T/Y],Rc,ℓ=∏ℓ′>ℓEc,ℓ′[T/Y].L_{c,\ell} = \prod_{\ell'<\ell} E_{c,\ell'}[T/Y],\qquad R_{c,\ell} = \prod_{\ell'>\ell} E_{c,\ell'}[T/Y].

The square marks the hole; it is not a stored field. The compiler emits one record constructor per summand, tagged by (c,ℓ)(c,\ell). Its fields are exactly the fields of cc other than ℓ\ell, in source order: the LL fields, then the RR fields. The record’s generated name encodes the tag, so it identifies the constructor and where the hole falls between the LL and RR fields.

Representing traversal histories

Kamot stores the path of frames with the most recently crossed frame at its accessible end (§ 2). Write ⟨A]\langle A] and [A⟩[A\rangle for forward and backward lists of AA, with the angle marking the accessible end:

data Forward a  = FNil | FCons a (Forward a)
data Backward a = BNil | Snoc (Backward a) a

Both keep elements in the displayed order: ⟨1,2,3]\langle1, 2, 3] is FCons 1 (FCons 2 (FCons 3 FNil))) and exposes 11, while [1,2,3⟩[1, 2, 3\rangle is Snoc (Snoc (Snoc BNil 1) 2) 3 and exposes 33.

An element context either stops at a terminal context in BB or passes through a frame L□RL\Box R of KK to the context of a child. Its finite-path presentation is the path equation DXT=μQ.(B+L×Q×R)D_XT = \mu Q.(B+L\times Q\times R) [1], where L×Q×RL\times Q\times R abbreviates the sum over the summands of KK. Each step contains one QQ, whatever the degree of Φ\Phi in YY: exactly one child continues towards the selected occurrence, and the frame stores all other fields on their own side of the hole.

A path lists its steps from the root down; step kk keeps the fields lkl_k left of its hole and rkr_k right of it. Rebuilding the value wraps each step around the rest of the path, so the surrounding fields, read left to right, are l1,…,lnl_1,\ldots,l_n, then the terminal bb, then rn,…,r1r_n,\ldots,r_1. In Figure 1, the path to G gives A and the subtree at B from the root step, then C, then G’s children, then D from the root step again. A history stores the same steps in a backward list, last step exposed. For a history HH, write before(H)\mathit{before}(H) for its left fields, first step to last, and after(H)\mathit{after}(H) for its right fields, last step to first.

Lemma 4.1 (Path–trail correspondence). For LL, RR, and BB independent of QQ, there is a bijection

μQ. (B+L×Q×R)≅[L×R⟩×B.\mu_Q.\ (B + L \times Q \times R) \cong[L \times R\rangle\times B.

It is order-preserving: if a path corresponds to (H,b)(H,b), then before(H)\mathit{before}(H), bb, after(H)\mathit{after}(H) lists the context’s stored fields in their original left-to-right order. Converting a path of nn steps, in either direction, takes O(n+1)O(n+1) structural work (§ 7) and allocates O(n+1)O(n+1) spine cells.

Proof. See Appendix § 24. □

Applied to the path equation, the lemma gives the element contexts DXTD_XT and the zippers ZTZ_T that focus an element:

DXT=[K⟩×B,ZT=[K⟩×B×X.(1)D_XT = [K\rangle\times B,\qquad Z_T = [K\rangle\times B \times X. \tag*{(1)}

For a list, data List a = Nil | Cons a (List a), a step has type XX, and the terminal context stores the rest of the list. So

ZT=[X⟩×T×X:Z_T = [X\rangle\times T \times X :

the history holds the elements before the focus, nearest exposed.

Trails for mutually recursive families

The rose tree of Figure 1 is not one-sort: its recursion passes through a list. Lowering (§ 3) turns the list field into a fresh sort List0 (Figure 2), giving the mutually recursive sorts Tree and List0. Indexing sorts by name, their IR bodies are ΦTree=X×YList0\Phi_{\mathrm{Tree}} = X \times Y_{\mathrm{List0}} and ΦList0=1+YTree×YList0\Phi_{\mathrm{List0}} = 1 + Y_{\mathrm{Tree}} \times Y_{\mathrm{List0}}. A path from a tree to its first child crosses Tree →\to List0 →\to Tree. Each frame records the parent sort it reconstructs and the child sort it accepts, so a trail has a fixed root sort and a changing current sort.

Formally, a family’s finite values form its simultaneous least fixed point

Ti=Φi(X,T1,…,Tm)(1≤i≤m).T_i = \Phi_i(X,T_1,\ldots,T_m)\qquad(1 \leq i \leq m).

Here ii names a parent sort and jj one of its recursive child sorts. Differentiating with respect to YjY_j, the type of an immediate child of sort jj, gives KijK_{ij}: the information needed to reconstruct an ii after returning from a jj. Differentiating with respect to XX gives BiB_i, the terminal context for a selected element field of sort ii:

Kij=(DYjΦi)[T1/Y1,…,Tm/Ym],Bi=(DXΦi)[T1/Y1,…,Tm/Ym].K_{ij} = (D_{Y_j}\Phi_i)[T_1/Y_1,\ldots,T_m/Y_m],\qquad B_i = (D_X\Phi_i)[T_1/Y_1,\ldots,T_m/Y_m].

Each summand of KijK_{ij} again splits at its hole as Lc,ℓ×Rc,ℓL_{c,\ell} \times R_{c,\ell}, for c∈Cic \in C_i and Ec,ℓ=YjE_{c,\ell} = Y_j, and its record’s name now also gives the sort ii. For the rose tree, KTree,TreeK_{\mathrm{Tree},\mathrm{Tree}} and BList0B_{\mathrm{List0}} are 00: a node has no tree field, and a List0 cell has no label. Finite paths form the least solution of this equation:

Ci=Bi+∑j∑c∈Ci∑ℓ:Ec,ℓ=YjLc,ℓ×Cj×Rc,ℓ.(2)C_i = B_i + \sum_j \sum_{c \in C_i} \sum_{\ell:E_{c,\ell}=Y_j} L_{c,\ell} \times C_j \times R_{c,\ell}. \tag*{(2)}

For the rose tree it reads

CTree=BTree+X×CList0,CList0=CTree×TList0+TTree×CList0.C_{\mathrm{Tree}} = B_{\mathrm{Tree}} + X \times C_{\mathrm{List0}},\qquad C_{\mathrm{List0}} = C_{\mathrm{Tree}} \times T_{\mathrm{List0}} + T_{\mathrm{Tree}} \times C_{\mathrm{List0}}.

A path from a root rr is thus a finite, well-sorted sequence of frames ending at some current sort ii, followed by a BiB_i. Theorem 4.2 represents it by a backward trail from rr to ii, nearest frame exposed:

Theorem 4.2 (Indexed path–trail correspondence). For every root sort rr, there is a bijection, order-preserving in the sense of Lemma 4.1,

Cr≅∑iTrail⁡(r,i)×Bi.C_r \cong\sum_i \operatorname{Trail}(r,i) \times B_i.

Here Trail⁡(r,i)\operatorname{Trail}(r,i) is the type of finite, well-sorted frame paths from rr to ii. Extending such a path by one KijK_{ij} frame and removing its nearest frame take constant structural work. Adding the selected XX field to its terminal context yields exactly one marked element occurrence in a value of root sort rr.

Proof. Use an accumulator whose current-sort index is part of its type. It starts empty at rr. On a summand Lc,ℓ×Cj×Rc,ℓL_{c,\ell} \times C_j \times R_{c,\ell} with c∈Cic \in C_i, append the ii-to-jj frame, which keeps both sides and its tag, and continue with current sort jj; on BiB_i, return the accumulator and that terminal. Frame order is unchanged. Conversely, start with BiB_i, remove each exposed final frame, and wrap the residual context between its LL and RR fields until the trail is empty. These two procedures are mutually inverse. Each transfer touches only one outer trail and frame constructor, while the terminal tag identifies the selected field. □

The generated target represents Trail⁡(r,i)\operatorname{Trail}(r,i) with a generalised algebraic datatype (GADT) indexed by the root and current sorts. Each frame record is indexed by the sort it rebuilds and the sort of its hole. For example, Frame_Tree_Node_1 represents the child-list hole in Node and has type Frame a Tree List0; each terminal record (Body) is indexed by its sort. For the rose tree, Kamot emits

data Trail a root current where
  BNil :: Trail a t t
  Snoc :: Trail a root parent -> Frame a parent child -> Trail a root child

Snoc extends a trail ending at a parent with a frame from that parent to a child. A trail cannot be extended with a frame for the wrong parent, and navigation cannot return through a mismatched frame. No runtime sort check or cast is needed.

Before lowering, Equation (1) with the types of § 2 gives

ZT=[X×List⁡T×List⁡T]×List⁡T×X.Z_T = [X \times\operatorname{List} T \times\operatorname{List} T] \times\operatorname{List} T \times X.

Kamot stores each such crumb as several indexed frames (§ 2).

Generating zipper operations

For every one-sort datatype, Kamot emits the zipper type ZTZ_T of Equation (1) as

data Frame a   = Frame_c_l E_c,0 · · · E_c,l−1 E_c,l+1 · · · E_c,a_c−1
                 (E_c,l = Y)
data Body a    = Body_c,l E_c,0 · · · E_c,l−1 E_c,l+1 · · · E_c,a_c−1
                 (E_c,l = X)
data Backward a = BNil (Backward a)
data Zipper a   = Cursor (Backward (Frame a)) (Body a) a

Frame has one constructor for each constructor cc and recursive field ℓ\ell of cc, and Body one for each element field. Each is cc with field ℓ\ell removed: it keeps the fields before ℓ\ell and those after it, in source order, reading X as a and Y as T a. For the list, Cons has fields X, Y, so Frame is Frame_Cons_1 a and Body is Body_Cons_0 (List a). The first field of Cursor, of type Backward (Frame a), is the trail: the saved frames from the root, nearest last.

One constructor-local rule generates the internal functions used by the interface of § 2. The proofs and cost bounds of § 6–§ 8 are stated over them. The displayed clauses omit sort indices; for a family, the seek and rise functions and the frames carry the indices of § 4.1. Call XX and YY fields active. Given a current position ℓ\ell in a constructor cc and a direction d∈{+,−}d \in\{+,-\} (forward or backward), the compiler finds the next active field ℓ′\ell' after ℓ\ell in direction dd; at constructor entry, ℓ\ell is −1-1 forward and aca_c backward. Each generated clause then has one of three outcomes: yield a direct element, descend through a recursive child after saving a frame, or return to the parent when no active field remains.

Let v\mathbf{v} be the variables bound by the constructor pattern and let v~ℓ′\widetilde{v}_{\ell'} omit vℓ′v_{\ell'}; HH is the trail. Write kc,ℓ′k_{c,\ell'} and bc,ℓ′b_{c,\ell'} for the constructors Frame_c_ℓ′ and Body_c_ℓ′. The entry function seek⁡d\operatorname{seek}_d finds the first element of a subtree in direction dd; the resumption function rise⁡d\operatorname{rise}_d continues in the parent once a child is finished. The three outcomes are emitted as

emit⁡d(c,ℓ)={Just⁡(Cursor⁡(H,bc,ℓ′(v~ℓ′),vℓ′))Ec,ℓ′=X,seek⁡d(Snoc⁡(H,kc,ℓ′(v~ℓ′)),vℓ′)Ec,ℓ′=Y,rise⁡d(H,c(v))no such ℓ′.(3)\operatorname{emit}_d(c,\ell)= \begin{cases} \operatorname{Just}(\operatorname{Cursor}(H,b_{c,\ell'}(\widetilde{v}_{\ell'}),v_{\ell'})) & E_{c,\ell'}=X,\\ \operatorname{seek}_d(\operatorname{Snoc}(H,k_{c,\ell'}(\widetilde{v}_{\ell'})),v_{\ell'}) & E_{c,\ell'}=Y,\\ \operatorname{rise}_d(H,c(\mathbf{v})) & \text{no such }\ell'. \end{cases} \tag*{(3)}

Constant fields (VV) are retained but never examined by this search.

The rule also produces the bodies of the public moves. A seek⁡d\operatorname{seek}_d clause matches a source constructor, saving a frame at each step down; a rise⁡d\operatorname{rise}_d clause matches the nearest frame and binds the completed child to the missing variable vℓv_{\ell}.

The public next and previous match the cursor’s terminal record, bind the focused element to vℓv_{\ell}, and continue after that position; openFirst and openLast are seek⁡d\operatorname{seek}_d from the empty history. All of these return Maybe (Zipper a). Generated code allocates a parent constructor only when traversal returns out of it; moving to another field of the same constructor builds the next Frame or Body record directly from the bound variables.

For the rose tree, Kamot emits these records, indexed by sort:

data Frame a parent child where
  Frame_Tree_Node_1 :: a -> Frame a Tree List0
  Frame_List0_List0Cons_0 :: (List0 a) -> Frame a List0 Tree
  Frame_List0_List0Cons_1 :: (Tree a) -> Frame a List0 List0

data Body a current where
  Body_Tree_Node_0 :: (List0 a) -> Body a Tree

Using Trail and Zipper from § 4.1, the forward clauses are:

seekTreeF :: Trail a root Tree -> Tree a -> Maybe (Zipper a root)
seekTreeF hs (Node v0 v1) =
  Just (Cursor hs (Body_Tree_Node_0 v1) v0)

seekList0F :: Trail a root List0 -> List0 a -> Maybe (Zipper a root)
seekList0F hs List0Nil =
  riseF List0Nil
seekList0F hs (List0Cons v0 v1) =
  seekTreeF (Snoc hs (Frame_List0_List0Cons_0 v1)) v0

riseF :: Trail a root current -> current a -> Maybe (Zipper a root)
riseF BNil _ = Nothing
riseF (Snoc hs frame) child = resumeF hs frame child
resumeF :: Trail a root parent -> Frame a parent child -> child a -> Maybe (Zipper a
  root)
resumeF hs (Frame_Tree_Node_1 v0) v1 =
  riseF hs (Node v0 v1)
resumeF hs (Frame_List0_List0Cons_0 v1) v0 =
  seekList0F (Snoc hs (Frame_List0_List0Cons_1 v0)) v1
resumeF hs (Frame_List0_List0Cons_1 v0) v1 =
  riseF hs (List0Cons v0 v1)

next :: Zipper a root -> Maybe (Zipper a root)
next (Cursor hs (Body_Tree_Node_0 v1) v0) =
  seekList0F (Snoc hs (Frame_Tree_Node_1 v0)) v1

Except for the empty-trail boundary and sort dispatch, these clauses instantiate Equation (3). The second resumeF clause returns from a Tree child to its List0 parent, changing the current sort accordingly. Entry is openFirst = seekTreeF BNil.

The same rule, with the order of active fields reversed, generates the backward functions seekTreeB, seekList0B, riseB, and resumeB, and from them previous and openLast. Moving between two element fields of one constructor replaces the Body record and leaves the trail unchanged; constructors that interleave elements and children need no further case. A search clause is one outcome of Equation (3) or the BNil boundary clause. A call to a sort-dispatch helper such as riseF counts as part of the outcome that makes it; § 7 charges its cost to that clause’s structural overhead.

The closing operation, close (here closeTree), rebuilds one parent per frame:

rebuild :: Frame a parent child -> child a -> parent a
rebuild (Frame_Tree_Node_1 v0) v1 = (Node v0 v1)
rebuild (Frame_List0_List0Cons_0 v1) v0 = (List0Cons v0 v1)
rebuild (Frame_List0_List0Cons_1 v0) v1 = (List0Cons v0 v1)

finish :: Trail a root current -> current a -> root a
finish BNil t = t
finish (Snoc hs frame) child = finish hs (rebuild frame child)

closeTree :: Zipper a Tree -> Tree a
closeTree (Cursor hs body x) = finishBodyTree hs body x

finishBodyTree :: Trail a Tree current -> Body a current -> a -> Tree a
finishBodyTree hs (Body_Tree_Node_0 v1) v0 =
  finish hs (Node v0 v1)

The number of Frame and Body constructors is linear in the number of active fields. Their retained fields and search clauses occupy O(∑c(1+ac)2)O(\sum_c (1 + a_c)^2) target syntax nodes. The ordinary family backend also specialises reconstruction helpers to each of the mm root sorts; its total output is therefore bounded by O(m∑c(1+ac)2)O(m \sum_c (1 + a_c)^2) nodes. This duplication changes code size but not transition counts.

Correctness by construction

The generated zipper operations are correct by construction: their clauses implement the ordered traversal of § 2. We prove this by relating the clauses of § 5 to a reference machine that can suspend at an element. Its stack κ\kappa is a finite list of records (c,ℓ,v^ℓ)(c,\ell,\widehat{v}_{\ell}): returning a child fills the omitted field and resumes after ℓ\ell. Stacks are sorted like trails: if cc is a constructor of sort pp and Ec,ℓ=Yp′E_{c,\ell}=Y_{p'}, pushing (c,ℓ,v^ℓ)(c,\ell,\widehat{v}_{\ell}) turns κ:Stack⁡(r,p)\kappa: \operatorname{Stack}(r,p) into a stack in Stack⁡(r,p′)\operatorname{Stack}(r,p'). The empty stack [ ]:Stack⁡(r,r)[\,] : \operatorname{Stack}(r,r) marks the root, and in each configuration below the value tt or constructor cc belongs to the current sort of κ\kappa.

There are three running configurations:

Enter⁡d(t,κ),Return⁡d(t,κ),Advance⁡d(c,v,ℓ,κ).\operatorname{Enter}_{d}(t,\kappa),\qquad\operatorname{Return}_{d}(t,\kappa),\qquad\operatorname{Advance}_{d}(c,v,\ell,\kappa).

There are also suspended configurations Yield⁡(c,v,ℓ,κ)\operatorname{Yield}(c,v,\ell,\kappa) and a terminal configuration End⁡\operatorname{End}. Define scan⁡d(c,v,ℓ,κ)\operatorname{scan}_{d}(c,v,\ell,\kappa) by selecting the next active field ℓ′\ell' strictly after ℓ\ell in direction dd:

Ec,ℓ′=X:Yield⁡(c,v,ℓ′,κ),Ec,ℓ′=Yp′:Enter⁡d(vℓ′,(c,ℓ′,v^ℓ′)::κ),no ℓ′:Return⁡d(c(v),κ).\begin{aligned} E_{c,\ell'} = X &: \quad\operatorname{Yield}(c,v,\ell',\kappa),\\ E_{c,\ell'} = Y_{p'} &: \quad\operatorname{Enter}_{d}(v_{\ell'},(c,\ell',\widehat{v}_{\ell'}) :: \kappa),\\ \text{no }\ell' &: \quad\operatorname{Return}_{d}(c(v),\kappa). \end{aligned}

Computing scan⁡d\operatorname{scan}_{d} inspects one constructor description at the meta level and costs no transition. The running configurations step as follows:

Enter⁡d(c(v),κ)⟶scan⁡d(c,v,ed(c),κ),\operatorname{Enter}_{d}(c(v),\kappa) \longrightarrow\operatorname{scan}_{d}(c,v,e_{d}(c),\kappa),
Return⁡d(t,(c,ℓ,v^ℓ)::κ)⟶scan⁡d(c,v^ℓ[ℓ:=t],ℓ,κ),\operatorname{Return}_{d}(t,(c,\ell,\widehat{v}_{\ell}) :: \kappa) \longrightarrow\operatorname{scan}_{d}(c,\widehat{v}_{\ell}[\ell:= t],\ell,\kappa),
Return⁡d(t,[ ])⟶End⁡,\operatorname{Return}_{d}(t,[\,]) \longrightarrow\operatorname{End},
Advance⁡d(c,v,ℓ,κ)⟶scan⁡d(c,v,ℓ,κ).\operatorname{Advance}_{d}(c,v,\ell,\kappa) \longrightarrow\operatorname{scan}_{d}(c,v,\ell,\kappa).

Here e+(c)=−1e_{+}(c)=-1 and e−(c)=ace_{-}(c)=a_{c} are the entry positions, and v^ℓ[ℓ:=t]\widehat{v}_{\ell}[\ell:= t] inserts tt at position ℓ\ell. Requesting another element resumes a yield as an Advance configuration; changing direction changes dd in that configuration. Each displayed transition costs one abstract step.

The encoding of reference configurations as generated terms mirrors the traversal state: a reference stack becomes the backward trail, a return record becomes kc,ℓk_{c,\ell}, and a yielded local position becomes (bc,ℓ(v^ℓ),vℓ)(b_{c,\ell}(\widehat{v}_{\ell}),v_{\ell}). Formally, stacks encode as trails, ⌈[ ]⌉=BNil⁡\lceil[\,]\rceil= \operatorname{BNil} and ⌈(c,ℓ,v^ℓ)::κ⌉=Snoc⁡(⌈κ⌉,kc,ℓ(v^ℓ))\lceil(c,\ell,\widehat{v}_{\ell}) :: \kappa\rceil= \operatorname{Snoc}(\lceil\kappa\rceil,k_{c,\ell}(\widehat{v}_{\ell})), so ⌈κ⌉:Trail⁡(r,p)\lceil\kappa\rceil: \operatorname{Trail}(r,p) for κ:Stack⁡(r,p)\kappa: \operatorname{Stack}(r,p).

The relation ≈\approx relates Enter⁡d(t,κ)\operatorname{Enter}_{d}(t,\kappa) and Return⁡d(t,κ)\operatorname{Return}_{d}(t,\kappa) to seek⁡d(⌈κ⌉,t)\operatorname{seek}_{d}(\lceil\kappa\rceil,t) and rise⁡d(⌈κ⌉,t)\operatorname{rise}_{d}(\lceil\kappa\rceil,t), respectively. A yield Yield⁡(c,v,ℓ,κ)\operatorname{Yield}(c,v,\ell,\kappa) relates to Just⁡(Cursor⁡(⌈κ⌉,bc,ℓ(v^ℓ),vℓ))\operatorname{Just}(\operatorname{Cursor}(\lceil\kappa\rceil,b_{c,\ell}(\widehat{v}_{\ell}),v_{\ell})). An Advance⁡d\operatorname{Advance}_{d} of that yield relates to a move in direction dd from its cursor, and End⁡\operatorname{End} relates to Nothing⁡\operatorname{Nothing}. Generated records are constructed explicitly from field references, so inspecting their outer tags terminates without forcing a source constructor.

Theorem 6.1 (Correctness of the generated operations). Fix an accepted family description. (1) Every generated search clause executes one step of the reference machine and demands the same source constructor, if any. (2) Every cursor obtained by entry, next, previous, and replace encodes a yield of the reference machine, and close reconstructs its root with all replacements. (3) On a finite, fully defined input, entry and moves select the occurrences of the ordered traversal, opposite moves undo each other, and replacement changes only the selected occurrence.

The proof rests on five lemmas: simulation, mixed-operation preservation, navigation, reversibility, and replacement. Appendix § 26 states them and sketches their proofs. Lean 4 mechanisms simulation for finite values of single self-recursive datatypes, in both directions (§ 10); the other lemmas, and simulation for families, are proved on paper.

A cursor is valid when entry followed by navigation and replacement produces it; cursor constructors are private (§ 2).

Cursor contracts and structural work

An operation contract states what an operation returns, how many control steps it takes, and which source constructors it forces, under stated preconditions. A control step is one reference transition of § 6: entering a constructor, resuming after a field, or returning through a frame. Source demand is the ordered list of source constructors the operation forces; only entry steps force one. The results are those of Theorem 6.1; the contracts add the step count and the demand order. Demand order matters for partial and infinite inputs, where forcing a subtree that the observation does not need can make it diverge.

The cursor operations have the following contracts. Here hh is trail depth, qq is the length of the operation’s reference search, and N,MN, M count constructor and element occurrences in the root.

operationcontrol stepssource demand
focus, replace00none
closeh+1h + 1none
openFirst/openLastqqordered reference search
next/previousqqordered reference search
traverse2N+M2N + Mcomplete forward traversal

Table 10.

Entry and moves search to the next yield or boundary. The count for traverse includes entry through openFirst and the final request that returns the boundary. An ordered reference search forces the constructors that the reference run matches, in the order it matches them. The table does not bound qq; for certified directions, § 8 bounds qq and the constructor demands, with uniform move bound q≤bd(h)q \le b_d(h) (Equation (5)).

The contracts have three preconditions. Operations on an existing cursor require a valid cursor (§ 6). The traversal count requires a finite total root: a finite, fully defined input. Certified termination of entry or a move also requires productive demanded roots: each requested source value exposes its outer constructor in finite time. The generated code does not check these preconditions, and no transition bound helps when a demanded source constructor is undefined.

Kamot emits each contract in a JSON report; Appendix § 25.§ 1 gives the work grammar, the trace descriptors, and the contract judgement.

Theorem 7.1 (Entry contract). Fix an accepted family, a direction dd, and a root value tt, and let RR be the reference run from Enter⁡d(t,[ ])\operatorname{Enter}_d(t, [\ ]) to its first Yield or End. Then openFirst (d=+d = +) or openLast (d=−d = -) on tt executes one generated search clause per step of RR, with the same source demand, on every finite prefix of RR. If RR ends after qq steps, the operation takes qq control steps and returns a cursor that encodes the final Yield, or Nothing at End.

Theorem 7.2 (Move contract). Fix an accepted family, a direction dd, and a valid cursor zz, and let RR be the reference run from Advance⁡d\operatorname{Advance}_d of the yield that zz encodes to the next Yield or End. Then next (d=+d = +) or previous (d=−d = -) from zz satisfies the conclusions of Theorem 7.1 for RR.

Theorem 7.3 (Local-operation contract). At a valid cursor of depth hh, focus, replace, and close take 00, 00, and h+1h + 1 control steps, respectively, without source demand.

Proof outline. Theorem 6.1 gives one clause per reference step with the same demand and makes every valid cursor encode a yield; the local operations satisfy their direct counts (Appendix § 25.§ 1). □\square

The structural cost model charges for inspecting an available constructor, allocating a constructor, and reading or writing a field reference. Fields are shared; copying a reference does not traverse its referent. Let a≥1a \ge1 bound all source constructor arities. For a fixed description Φ=(Φ1,…,Φm)\Phi= (\Phi_1,\ldots,\Phi_m), tag dispatch and constructor arities are bounded, so each search clause has bounded structural cost independent of input size and depth. We write OΦO_{\Phi} when the hidden constant may depend on Φ\Phi.

Theorem 7.4 (Structural work). A search of qq reference steps executes exactly qq generated search clauses and incurs OΦ(q+1)O_{\Phi}(q+1) structural work and allocation. A complete traversal in one direction of a finite input, including the final boundary result, executes exactly qq generated search clauses:

q=2N+M,(4)q = 2N + M, \tag*{(4)}

where NN counts source constructor occurrences across the family’s unfolding and MM counts element occurrences. Its structural work is OΦ(N+1)O_{\Phi}(N+1). At a cursor of depth hh, focus and replace have constant structural overhead, and close takes OΦ(h+1)O_{\Phi}(h+1) work.

Proof. The first statement follows from part 1 of Theorem 6.1. One emitted clause matches a bounded number of tags and allocates a bounded number of records, each containing at most aa field references. The backward trail requires one exposed-end update, never a scan of the history. Taking the largest clause cost gives the constant.

In a complete traversal, every constructor is entered once and returned from once, including the root’s final return. These contribute NN entry and NN return clauses. Each element yields once and is advanced past once, contributing MM move clauses. No other search clause is executed. This proves Equation (4), in either direction. Since M≤aNM \le aN, the structural bound follows for fixed Φ\Phi.

Reading or replacing the focus accesses a fixed cursor field. Closing reconstructs the terminal constructor and then removes one frame for each of the hh ancestors, doing bounded work per frame; the final BNil case returns the rebuilt root and is not counted as a step. No off-path constructor is visited. □

The traversal count assumes no intervening calls to close. Element replacement preserves the shape and hence the count. Sharing in the source value is counted by unfolding: a shared subtree reached in two distinct positions is traversed twice. Newly allocated cursor records occupy OΦ(h+1)O_{\Phi}(h+1) space at a suspended position; the data they reference can be arbitrarily large. Retaining old cursor versions can also retain their referenced data.

A single move need not cost O(h+1)O(h+1). For

data Sparse a = Empty | Item a | Split (Sparse a) (Sparse a)

a move between two elements can traverse an arbitrarily large intervening empty subtree. § 8 gives a condition on the datatype under which a function of hh bounds every move.

The structural model does not count the evaluation of source thunks or elements, garbage collection, or client work.

Compositional contracts for finite observations

We infer bounds on the transitions and constructor demands needed to reach the next yield or boundary, without inspecting the input. The analysis composes constructor summaries across sorts and then along the finite trail.

For a coinductive input T∞=νY. Φ(X,Y)T^{\infty} = \nu Y.\,\Phi(X,Y), a reachable cursor still has a finite history. Its finite-path contexts have the form

C∞=μQ. (B∞+K∞×Q)≅[K∞]×B∞.C_{\infty} = \mu Q.\,(B_{\infty} + K_{\infty} \times Q) \cong[K_{\infty}] \times B_{\infty}.

where K∞K_{\infty} and B∞B_{\infty} are the recursive and element derivatives evaluated at T∞T^{\infty}. Stored siblings may be infinite; the trail spine remains finite [1]. For families, these contexts are indexed by sort as in § 4.1. Enumeration is responsive if each request terminates with a cursor or boundary.

Corollary 8.1 (Finite observations). If demanded roots are productive, every finite reference observation is returned by the generated search with the same source demands. Thus generated cursor enumeration is responsive whenever every requested reference observation is finite.

Proof. Theorems 7.1 and 7.2 give the same finite sequence of steps and demands. Each demand terminates, and navigation inspects no element or constant field. □

An infinite label-free branch can still prevent a search from reaching a sibling; the analysis must bound the search itself.

Composing prefixes across sorts

We first bound, for each sort, the search that enters one of its values, by composing constructor summaries across the sorts it may reach before a yield. Composition is already necessary for the lowered rose tree: List0Cons carries no label, but its first child, a Tree, yields immediately. The datatype dependency graph is cyclic, while the dependencies followed before a yield are acyclic.

A sort is nullable when some finite traversal of a value of that sort returns without yielding. Nullability Null⁡\operatorname{Null} and prefix edges i→dji \to_d j in direction dd are the least relations closed under

c∈Cic has no X field∀ℓ. Ec,ℓ=Yj⇒Null⁡(j)Null⁡(i)c∈CiEc,ℓ=Yj∀ℓ′≺dℓ active. Ec,ℓ′=Yj′∧Null⁡(j′)i→dj\frac{c \in C_i \quad c\text{ has no }X\text{ field} \quad\forall\ell.\ E_{c,\ell}=Y_j \Rightarrow\operatorname{Null}(j)}{\operatorname{Null}(i)} \qquad \frac{c \in C_i \quad E_{c,\ell}=Y_j \quad\forall\ell'\prec_d\ell\text{ active}.\ E_{c,\ell'}=Y_{j'}\land\operatorname{Null}(j')}{i\to_d j}

Here ℓ′≺dℓ\ell'\prec_d\ell means that field ℓ′\ell' precedes ℓ\ell in direction dd. Prefix edges pass earlier nullable children because those children may return empty.

A summary records separate yield and return outcomes, each with a pair (w,n)(w,n) bounding transitions and demanded constructors. Impossible outcomes are omitted. The entry summary Ej\mathcal{E}_j covers a search that enters a value of sort jj, up to its first yield or up to, but excluding, its return; the continuation it returns to pays for that return. We evaluate entry summaries in dependency order wherever the reachable prefix graph is acyclic; an unresolved cycle gives unknown.

Let S(u)S(u) summarise a field suffix uu, excluding its initial control action. An empty suffix returns with (0,0)(0,0), an element yields with (0,0)(0,0), and constants are skipped. For a recursive field YjY_j,

S(Yju).yield⁡=max⁡(Ej.yield⁡, Ej.return⁡+(1,0)+S(u).yield⁡),S(Yju).return⁡=Ej.return⁡+(1,0)+S(u).return⁡.\begin{aligned} S(Y_ju).\operatorname{yield} &= \max\bigl(\mathcal{E}_j.\operatorname{yield},\ \mathcal{E}_j.\operatorname{return}+(1,0)+S(u).\operatorname{yield}\bigr),\\ S(Y_ju).\operatorname{return} &= \mathcal{E}_j.\operatorname{return}+(1,0)+S(u).\operatorname{return}. \end{aligned}

Addition and maximum are componentwise. An alternative containing an impossible outcome is omitted before its other terms are evaluated; an outcome with no remaining alternatives is impossible. The (1,0)(1,0) charge pays for the child’s return. Entry adds (1,1)(1,1) for matching the constructor and takes the maximum over constructors. A terminal continuation resumes the fields after a yielded element, and a frame continuation resumes the fields after a returning child; each adds (1,0)(1,0) for that resuming transition to its suffix summary. Demands count occurrences, not distinct heap objects.

Entry alone does not certify a move: a constructor with a label followed by an endless label-free child yields on entry but diverges on resumption. We therefore analyse every terminal and frame continuation. If all are bounded, let (wB,nB)(w_B,n_B) and (wK,nK)(w_K,n_K) be the componentwise maxima over the possible outcomes of terminal and of frame continuations, using (0,0)(0,0) for an empty collection. The move certificate at depth hh is

q≤bd(h)=wB+h wK+1,#demands≤nB+h nK.(5)q \le b_d(h)=w_B+h\,w_K+1,\qquad\#\text{demands}\le n_B+h\,n_K. \tag*{(5)}

The final 11 covers a possible return from the root. The report also retains the individual sort and suffix summaries.

Theorem 8.2 (Compositional family contracts). Fix an accepted family and direction dd, with productive demanded roots. A bounded root-entry summary Er\mathcal{E}_r guarantees a yield or boundary within max⁡(Er.yield,Er.return+(1,0))\max(\mathcal{E}_r.\mathrm{yield},\mathcal{E}_r.\mathrm{return} + (1, 0)) transitions and constructor demands. An emitted move certificate guarantees a yield or boundary within the bounds of Equation (5) from every valid cursor at depth hh. Both guarantees hold for generated searches on finite or infinite values, including auxiliary sorts.

Proof outline. Induct over the acyclic prefix order and each constructor’s field suffixes. Every child that returns empty witnesses nullability, so prefix edges cover all children a search can enter before yielding. Summing the terminal segment, at most hh frame segments, and the root return gives the move bound. Appendix § 22 gives the full proof. □

For the rose tree, List0 is nullable and Tree is not. The forward prefix graph has only List0 -> Tree, with entry summaries

yieldreturn
Tree(1,1)(1, 1)impossible
List0(2,2)(2, 2)(1,1)(1, 1)

Table 11.

Both terminal and frame continuation maxima are (3,2)(3, 2), giving 4+3h4 + 3h transitions and 2+2h2 + 2h demands per move, where hh counts lowered frames, including list frames. Backward traversal has a prefix cycle and remains uncertified. Adding Silent also makes forward traversal uncertified: arbitrarily many label-free nodes may precede the next label. For one-sort datatypes, a syntactic check suffices: in the direction of the move, every recursive constructor has an element field before its first recursive field (Appendix § 16).

Charging each frame its own outcome. Equation (5) charges every frame the componentwise maximum over all frame outcomes, although only the last segment of a move can yield. The report keeps each terminal and frame summary, so a client that knows the trail can use a sharper bound.

Theorem 8.3 (Trail-sum bound). Under the assumptions of Theorem 8.2, let a valid cursor have terminal record kind τ\tau and trail frames f1,…,fhf_1,\ldots,f_h, nearest first, let BτB_\tau and KfK_f be the summaries of their continuations, and suppose these summaries are bounded, as they are when a move certificate is emitted. A move reaches a yield or the boundary within the componentwise maximum of Bτ.yieldB_\tau.\mathrm{yield}, of Bτ.return+∑i<mKfi.return+Kfm.yieldB_\tau.\mathrm{return}+\sum_{i<m}K_{f_i}.\mathrm{return}+K_{f_m}.\mathrm{yield} for 1≤m≤h1\le m\le h, and of Bτ.return+∑i≤hKfi.return+(1,0)B_\tau.\mathrm{return}+\sum_{i\le h}K_{f_i}.\mathrm{return}+(1,0), omitting terms with an impossible outcome.

Proof. As in the proof of Theorem 8.2, Lemma G.2 bounds the terminal segment by BτB_\tau and the iith frame segment by KfiK_{f_i}. All earlier segments return; only the last can yield. □

Let By\mathcal{B}^y, Br\mathcal{B}^r, Ky\mathcal{K}^y, Kr\mathcal{K}^r be the componentwise maxima of the yield and return outcomes of terminal and frame continuations, taking (0,0)(0,0) when no continuation has that outcome. For h≥1h\ge1, Theorem 8.3 gives the uniform bound

max⁡(By, Br+(h−1)Kr+Ky, Br+hKr+(1,0)).(6)\max(\mathcal{B}^y,\ \mathcal{B}^r+(h-1)\mathcal{K}^r+\mathcal{K}^y,\ \mathcal{B}^r+h\mathcal{K}^r+(1,0)). \tag*{(6)}

For the rose tree, By=Ky=(3,2)\mathcal{B}^y=\mathcal{K}^y=(3,2) and Br=Kr=(3,1)\mathcal{B}^r=\mathcal{K}^r=(3,1), so the demand bound falls from 2+2h2+2h to 2+h2+h and the transition bound stays 4+3h4+3h. For a label in a value of sort Tree, let δ\delta count its ancestors and the earlier siblings along its path, so h=2δ+sh=2\delta+s. Theorem 8.3 gives 4+4δ+s4+4\delta+s transitions and 2+δ2+\delta demands (Appendix § 22). Only the demand bound depends solely on source depth. At G, δ=2\delta=2, s=1s=1, and h=5h=5. § 10.1 checks these bounds on generated values.

Completeness. Call a family inhabited when every sort occurs in some finite value of a root sort and has a finite value that contains an element, and every constant field type has a value.

Theorem 8.4 (Completeness). Fix an inhabited accepted family and a direction dd.

  1. For each root sort rr, ErE_r is bounded if and only if one constant bounds the transitions of root entry on all finite values of sort rr.

  2. A move certificate is emitted if and only if some function of hh alone bounds the transitions of every move from a valid cursor at depth hh on finite values.

  3. If no move certificate is emitted, some infinite value whose constructors are all defined has a valid cursor whose move diverges.

Parts 1 and 2 also hold with constructor demands in place of transitions.

Proof outline. Soundness is Theorem 8.2. Repeating a reachable prefix cycle gives unbounded finite entry costs. Inhabitation places each unknown continuation after a valid cursor at fixed depth; repeating its cycle then gives unbounded move costs, and following it forever gives a productive input with a divergent move. Appendix H gives the constructions. □

For an inhabited family, the moves in each direction are therefore either bounded by an affine function of hh or bounded by no function of hh. Completeness is relative to Kamot’s traversal and lowering: a loopless traversal [7] or a snoc lowering of lists can bound moves that this one cannot. The proof uses inhabitation: a frame whose child sort holds no element in any finite value cannot occur in a valid cursor’s trail on a finite value, yet its continuation is analysed and can be reported unknown.

Using the bounds

The resumable backend exposes each reference transition as step, retaining its control position, typed trail, and strict cached depth. The driver runFor with budget β\beta executes at most max⁡(0,β)\max(0,\beta) transitions and returns a result or suspended state. For β>0\beta> 0, a scheduler runs next directly when bd(h)≤βb_d(h) \le\beta; otherwise, or without a certificate, it runs runFor β\beta.

Corollary 8.5 (Contract-directed slicing). For a move from a valid cursor on productive demanded roots, each scheduler invocation with budget β>0\beta> 0 executes at most β\beta reference transitions. Positive-budget resumptions preserve the unbounded search’s results and ordered demand trace.

Proof. Theorem 8.2 bounds the direct case; the driver’s counter bounds each slice. Suspension preserves the search state. □

Appendix E measures the scheduling policy.

Admitting a complete observation. A client can reserve both a work budget β\beta and a demand budget χ\chi. It admits a move when a certificate is present and

bd(h)≤β,nB+h nK≤χ.b_d(h) \le\beta,\qquad n_B + h\,n_K \le\chi.

The test reads only the certificate and cached depth. An admitted move completes within both budgets on productive input. Rejection demands no source but may defer a move whose actual cost fits the budgets. The dynamically budgeted alternative in § 10.2 spends demand credit only on entry, allowing returns and advances without forcing source constructors.

If a terminal suffix has no return outcome, the search must yield before consulting the trail. Its local work and demand bounds then suffice, even at large depth. Inspecting the terminal tag does not force its saved subtrees. Appendix D evaluates this refinement.

Resumable eager folds

A fold replaces completed subtrees by their results. Following McBride’s dissection [23], its frames distinguish completed results JJ from pending source subtrees TT. For the rose tree, the container-level frame is

Frame⁡fold(X,J,T)=X×[J⟩□⟨T].\operatorname{Frame}_{\mathrm{fold}}(X,J,T)=X\times[J\rangle\Box\langle T].

Completed siblings lie to the left of the hole and pending siblings to its right; setting J=TJ=T recovers the ordinary frame. After any finite execution prefix, the completed spine is finite even when pending subtrees are infinite.

Kamot implements this distinction after container lowering, with indexed frames and one result type JJ shared by all sorts. The algebra for sort ii has type Φi(X,J,…,J)→J\Phi_i(X,J,\ldots,J)\to J. Appendix § 18 gives the construction and discusses extending it to separate result types per sort.

The reference fold exposes a constructor, evaluates its recursive children left to right, and applies the algebra to the completed layer. Child and algebra results are forced to weak head normal form (the outer constructor or function closure); element and constant fields remain lazy unless demanded by the algebra. The machine therefore enters even children ignored by the algebra.

The interface provides start, step, pending, runFor, and run. The step clauses are nonrecursive; each transition descends, applies the algebra, or returns. A completed fold over NN constructors therefore takes exactly 3N3N transitions, one of each kind per constructor, and agrees with the reference eager fold (Theorem C.1). Fuelled execution partitions this sequence into resumable slices. Source forcing and algebra work lie outside the structural count, so fuel cannot interrupt a divergent thunk or callback. On infinite input, each fuelled slice still suspends after finitely many transitions if its demands and algebra applications terminate, although the fold never finishes.

Theorem C.2 (Appendix § 18) covers the cursor and eager-fold backends: compilation terminates, the generated types follow the indexed schemas, and each backend satisfies its stated contracts.

Complete batch plans. Cursor enumeration and an eager fold can both collect the elements of a finite total root in field order. Appendix § 17 gives a selector based on their 2N+M2N+M and 3N3N control counts, and Appendix § 17.§ 1 measures its choices. These counts exclude source forcing and output construction and do not predict elapsed time.

Evaluation

Kamot implements the family IR and declaration frontend of § 3 in OCaml. It emits JSON contracts and Haskell code that uses indexed GADTs without casts or reflection. After validating the generated code and certificates, we test four claims:

  • (C1) Every tested direction without a move certificate has a checked productive input with a divergent move. Both emitted and refined bounds hold on generated values (§ 10.1).

  • (C2) Admission from emitted bounds answers every local query, as fuelled search does; on long returns it avoids discarded evaluations but can lose answers (§ 10.2).

  • (C3) Generated cursors match the handwritten indexed stack’s allocation, with overlapping timing ranges, and are several times faster than generic zippers (§ 10.3).

  • (C4) For families of up to 32 sorts and 64 constructors, fresh -O2 builds take 0.16–2.76 s for cursors and 0.27–3.46 s for folds; the largest cursor module is 222 KiB (Appendix § 21.§ 6).

The generator’s instrumented one-sort variant counts entry, return, and advance clauses. Three independent tools check the output. A Python validator checks the work ASTs and composition metadata in the reports. A certificate checker reads the source family and prefix certificate, without importing the compiler or inference code, and checks nullability, acyclicity of prefix dependencies, local bound inequalities, and composition along the trail. A source interpreter compares execution traces and results with generated Haskell, including on partial and infinite-prefix inputs. The suite checks 81 source families and rejects five deliberately corrupted certificates. On nine families, 201 comparisons check that generated resumable Haskell and the source interpreter agree on traces and results.

The artifact’s Lean 4 development proves the finite one-sort results in both directions: lockstep simulation for a generated dispatch table, with the same source constructor matched at each step (part 1 of Theorem 6.1), termination, root-entry and move bounds (Theorem 8.2), trail-sum bounds (Theorem 8.3, under a move certificate), and completeness for transitions and demands (parts 1 and 2 of Theorem 8.4).

The completeness witnesses are reached by root entry and finitely many completed moves. A separate forward model of constructor unfoldings proves part 3: a productive root leads to a cursor whose next move diverges. This model retains saved fields and reconstructed return values. The finite backward results use mirroring and a Lean formulation of the compiler’s backward analysis. Families, lowering, infinite-input bounds, and the link to printed Haskell remain unmechanised. For one sort, the prefix analysis reduces to a syntactic guard. The development uses only core Lean and its standard axioms.

Source fields in generated records remain lazy; cached depth and fuel counters are strict. The 201 trace comparisons pass under both runghc and ghc -O2, including partial inputs with undefined unvisited fields. Across 108 configurations, the -O2 admission audit checks that producer invocations equal recorded Enter demands. Separate tests show that zero demand credit leaves undefined children unforced, while zero fuel leaves the search state unforced. These tests observe logical traces, counts, and partial-input behaviour, not actual thunk-forcing order in optimised code. Part 1 of Theorem 6.1 relates each generated pattern match to a reference demand; that compiled code forces source constructors in this order is tested, not proved.

The runtime harness compares Kamot cursors with a handwritten explicit stack, direct recursive rescan, and two generic baselines: zippers-0.3.2’s generic Jacket/Path [19], and a GHC 9.12 port of McBride’s Diss zipper [23]. It records elapsed time, runtime system (RTS) allocation, and post-collection live bytes independently of clause counts. The cursor, scheduling, and batch-crossover measurements use GHC 9.12.1 at -O2 on an Apple M3 Max running macOS 26.5.2, with +RTS -T -A32m; the one-sort cursor-comparison and fold builds also use -threaded. The artifact retains raw measurements, generated sources, and build metadata. We report medians and ranges of seven fresh-process samples (three for compiler builds), treating overlapping ranges as unresolved. Appendix § 21 gives detailed protocols and validation coverage.

Certificate precision

We analyse a corpus of 19 datatype models, each with a forward and a backward direction, and the trace suite’s 81 generated families. The analysis certifies 10 of 38 corpus directions. All 28 unknown corpus directions, all 82 unknown generated directions, and every unknown root entry have independently checked divergence witnesses (Appendix § 21). Truncating an entry witness gives unbounded finite entry costs; for a move witness, costs grow while cursor depth stays fixed.

For each certified direction, an independent interpreter checks every move on 200 generated finite values. No move exceeds its bound, and 7 of the 10 emitted transition bounds are attained exactly (Table 1). Unusually many moves, which return through every frame, attain them; moves that yield reach at most 0.86 of the bound (medians 0.29–0.67). On all 3,847 moves, observed costs never exceed the trail-sum bound of Theorem 8.3, which never exceeds the separated bound, which never exceeds the emitted one; some move reaches its trail-sum bound in every direction. For rose-tree values of sort Tree, the source-tree bounds 4+4δ+s4 + 4\delta+ s and 2+δ2 + \delta are attained and never exceeded. The values are shallow (h≤7h \le7), so these checks test the bounds, not their slopes.

DatatypeDir.EmittedSeparatedMovesRatio
Listfwd4+h4 + h; 14+h4 + h; 1901.00
Listbwd2+h2 + h; 02; 0901.00
Event logfwd4+h4 + h; 14+h4 + h; 11121.00
Event logbwd2+h2 + h; 02; 01121.00
Rose treefwd4+3h4 + 3h; 2+2h2 + 2h4+3h4 + 3h; 2+h2 + h3521.00
File systemfwd4+3h4 + 3h; 2+2h2 + 2h4+3h4 + 3h; 2+h2 + h2461.00
Data.Map shapefwd6+3h6 + 3h; 2+h2 + h6+3h6 + 3h; 2+h2 + h1781.00
Located modulefwd5+3h5 + 3h; 2+2h2 + 2h4+3h4 + 3h; 2+h2 + h7150.88
Annotated lambdafwd3+2h3 + 2h; 1+h1 + h2+h2 + h; 11,0770.67
Postfix lambdabwd3+2h3 + 2h; 1+h1 + h2+h2 + h; 18750.67

Table 1. Certified directions in the 19-datatype corpus. Emitted gives the transition and demand bounds of Equation (5); Separated gives those of Equation (6) for h≥1h \ge1. Moves is the total over 200 generated values (empty values contribute none); Ratio is the largest observed transition count divided by the emitted bound. The other 28 directions have divergence witnesses.

divergence witnesses are checked independently of Theorem 8.4, which guarantees that they exist for inhabited families. The models admit unrestricted values: the Data.Map shape, for example, omits balance invariants, so precision on constrained library values is not established.

In the syntax models, annotation position explains the outcomes: annotations before children give forward certificates, and annotations after children give backward ones. Unannotated applications can delay the next variable indefinitely. Repeated JSON nulls, DOM comments, YAML sequences, and empty trie nodes prevent bounds in either direction.

Admission before source demand

As an application, a prefetching service uses the emitted bounds to decide whether to start a query on the mutually recursive Expr/Decl family before an edit may cancel it (Appendix § 19). In local workloads, certified admission answers all 256 queries, while deferring every query until after the edit loses half. On long returns with eight demand credits and 50% cancellation, it avoids 1,024 discarded constructor evaluations and returns the same 128 answers as fuelled search, but blanket deferral does the same there; at larger budgets conservative bounds lose 13–15 answers. The study models a scheduling kernel, not editor responsiveness.

Comparison with handwritten and generic cursors

An annotation-service session makes 2,048 successive requests on a depth-4,096 skewed syntax tree and edits every 64th annotation. The zippers baseline takes an explicitly written preorder traversal; McBride’s dissection uses an ordered polynomial encoding and generic zipper moves (Table 2).

Time includes navigation, edits, and reconstruction; the dissection port also converts its polynomial result back to the native tree inside that interval. The dissection port’s navigation and edits alone take 270 ns per request, still above the generated cursor’s complete-session time. The generated cursor takes similar time to the handwritten stack and allocates fewer bytes in this workload. On a mutually recursive syntax family, a separate comparison with an independently handwritten, sort-indexed stack (Appendix § 21.§ 5) gives identical per-request allocation and overlapping timing ranges. An unindexed handwritten stack is faster on a deep chain of lets (38 versus 58 ns per request) but allocates more (309 versus 253 bytes). Separate fresh processes measure live heap after checking that all implementations produce equivalent outputs. Appendix § 21 gives the dissection phase breakdown, the family comparison, full protocols, the streaming-repair workload, and retained-state details.

ImplementationCodeBoundns/requestbytes/requestlive KiB
Kamot cursordeclarationyes107200426
Handwritten explicit stack cursorno113263394
McBride generic dissectionencodingno5601,0581,273
External zipperstraversalno6904,2373,126
Direct recursive rescansearchno4,94019,045394

Table 2. Incremental annotation: median time and allocation per request; live heap for one retained state. Code identifies the code written for each datatype; Bound indicates an emitted move bound.

Related work

Derivatives, containers, and dissections. Huet’s zipper [15] pairs a focus with a one-hole context; McBride [22] calculates these contexts for regular types. Container derivatives cover inductive and coinductive fixed points, including finite paths into potentially infinite values [1]; indexed containers give normal forms for strictly positive families [5]. Our closest predecessor, dissection [23], represents suspended traversals with contexts whose processed and pending fields may have different types. It derives generic navigation and tail-recursive catamorphisms; our fold backend adopts its processed/pending distinction. Kamot specialises these constructions to ordered families and derives contracts for their generated operations.

Generic zippers. Generic Haskell derives zippers from fixed-point datatype descriptions [14]. The multirec zipper indexes its stack by root and focus types for mutually recursive families [28]. Our indexed Trail GADT (Theorem 4.2) specialises this construction to generated first-order frames; its path equation (2) uses the path interpretation of a linear system’s least solution due to Kleene and Conway [8]. Heterogeneous Data-based zippers [3] support broader navigation; we exclude arbitrary Data-instance graphs. Kiselyov derives a zipper from any traversal by capturing its delimited continuation [17, 18]; its cursor is the suspended traversal, without a typed trail or cost bound.

Data-structure and resource-guided synthesis. Data representation synthesis compiles relational specifications through user-chosen decompositions [13]; Cozy synthesises collections from retrieval specifications [21]. Resource-guided synthesis prunes type-directed search with user-supplied bounds, producing programs correct by construction [20]. These systems take operation specifications or bounds as input. Kamot takes a datatype declaration, fixes one representation, the derivative trail, and emits its bound.

Grammar analyses and productivity. With sorts as nonterminals and elements as terminals, Null (§ 8.1) is grammar nullability, forward prefix edges form the left-corner relation, and cycles express left recursion [4], or right recursion in the backward direction. Parsing expression grammars use a similar fixed-point check to reject left recursion and ensure termination [11]. That check answers yes or no. Our analysis separates yield from return, covers entry and every resumption, and weights the relation with transition and demand bounds; these bounds compose along the trail and transfer to generated code.

Productivity analyses establish that lazy definitions produce every finite output prefix, using sufficient conditions on list equations [27], sized types [2, 16], or a decision procedure for pure stream specifications [10]. We assume a productive source and ask whether its traversal is productive for every input of a datatype. Stream processors typed by a least fixed point nested in a greatest one take finitely many input steps per output [12]; a certified move is such a processor with an explicit bound on its inductive part. Constant-delay enumeration bounds time between answers after preprocessing [6, 26]; our bounds need no preprocessing but grow with trail depth.

Folds and first-order machines. Our fold language follows recursion schemes [24]. First-order stacks descend from continuation-based interpreters [25] and defunctionalised machines [9]. We apply this pattern to a restricted eager language: frame payloads come from ordered derivative contexts, and contracts count structural transitions, source forcing, and client algebra separately.

Conclusion and Limitations

This paper showed that the derivative-based zipper of an ordered regular datatype can be compiled together with a bound on the work and source demand of each move. The analysis that produces these bounds rests on keeping the cost of a search that yields separate from that of a search that returns. With this separation, a search that must yield before it reaches a saved frame is bounded independently of the trail, and summaries computed for different sorts can be composed. Container lowering is what lets the same rules apply to the rose tree, whose list cells carry no label of their own.

In our experience, whether a direction is certified depends more on the order of fields than on the overall shape of the datatype. The rose tree, for example, is certified forward but not backward, and for a single datatype Appendix § 16 reduces the question to a syntactic test on field order.

The evaluation also shows where the bounds are loose. Only boundary moves, which return through every frame, reach the emitted transition bound, while moves that yield stay below 0.86 of it. The trail-sum bound is considerably closer, although Kamot does not yet emit it. In the admission study, the bounds saved source evaluations when queries were cancelled during long returns, but at larger budgets their conservatism cost 13–15 answers that fuelled search delivered.

Several limitations remain. Kamot accepts only the regular, strictly positive language of § 3, and its folds use a single result type for all sorts. We test, but do not prove, that compiled Haskell forces source constructors in the reference order, and the Lean development covers only single self-recursive datatypes; families, container lowering, and bounds on infinite inputs are proved on paper. Finally, we have not yet evaluated access patterns beyond those in § 10, or integration into an interactive editor.

AI Use

The authors used Claude Opus 5.5 (Anthropic, model claude-opus-5-5), accessed through Claude Code, and GPT-6 Astra (OpenAI, model gpt-6-astra), accessed through Codex, from July through November 2026. The tools were used to revise and edit text; to implement parts of the compiler prototype, the benchmarks, and the validation checkers; and to draft proof arguments, the Lean development, and tests. The system design, the theorems, and the claims are the authors’ own. The authors reviewed all generated text, code, and proofs, checked the correctness of every reported result, and take full responsibility for the content of this paper. Reported measurements come from the benchmark and validation programs in the artifact. The one-sort results listed in § 10 are mechanised in Lean 4; the other proofs are not mechanised.

Data-Availability Statement

The artifact is available at https://doi.org/10.5281/zenodo.24193628. It contains Kamot, the independent checkers, the benchmarks with raw results, and the Lean 4 development, which covers single self-recursive datatypes only. Timings are machine-dependent. We will submit the artifact for Artifact Evaluation.

References

The local entry condition

For a one-sort datatype, a local syntactic check suffices to certify that moves in one direction are productive. Call Φ\Phi entry-guarded in direction dd when every constructor containing a recursive field has an element field before its first recursive field in direction dd. Equivalently, its first active field is XX. Nonrecursive constructors impose no condition. The check takes one pass over the fields and is independent of the input value.

Theorem A.1 (A sufficient productivity certificate). Suppose Φ\Phi is entry-guarded in direction dd and let f≥0f \ge0 bound its number of recursive fields per constructor. On productive demanded roots, entry in direction dd yields or terminates in at most two search clauses. A move in direction dd from a valid cursor at depth hh yields or terminates within qq search clauses, where

q≤gd(h)=1+(2f+1)(h+1).(7)q \le g_d(h) = 1 + (2f + 1)(h + 1). \tag*{(7)}

In particular, repeated moves in that direction are productive, even when off-path fields are infinite.

Proof. On entering a constructor with any recursive field, the guard makes the first active field an element, so entry yields without descending. A nonrecursive constructor either yields an element or has no active fields and returns immediately. Root entry therefore costs one clause to yield, or one entry and one return clause to terminate.

For a move, count its initial advance clause. Before its next yield, every newly entered child is either an immediate yield or an empty nonrecursive constructor; the latter costs one entry and one return clause. Thus a search cannot build an unbounded chain of new frames without yielding. It can finish only the current constructor and its hh existing ancestors. At most ff previously unvisited recursive fields per such constructor cost at most two clauses each, and completing each of these h+1h+1 constructors costs at most one further return clause. Adding these costs gives Equation (7). The demanded roots are available in finite time by assumption, so the finite clause bound implies termination of the search.

Batch-plan selection details

The cursor and fold contracts expose different capabilities and control costs. A client can choose a plan from these contracts by specifying the required result and meeting the plan’s preconditions.

The cursor and eager-fold batch plans are compared only for a common, explicitly declared workload. For a finite total root tt, let elements⁡Φ(t)\operatorname{elements}_{\Phi}(t) be the direct elements of tt in the forward field order of § 3. A cursor client obtains this result by recording every focus of a complete forward traversal. A fold client uses the algebra whose direct-element field denotes a singleton sequence and whose recursive fields denote their already collected sequences, concatenated in field order. The implementation represents sequences as difference lists (functions that prepend a sequence to a supplied tail); their composition and final list construction are client work, outside the machine transition count.

Lemma B.1 (Common ordered-elements batch semantics). For every finite total root tt, complete cursor enumeration and the eager fold with the ordered-elements algebra both return elements⁡Φ(t)\operatorname{elements}_{\Phi}(t).

Proof. The cursor result follows from the traversal specification: every direct element is yielded once, in constructor-field order. For the fold, induction on tt shows that each completed recursive field denotes the elements of that child. The layer algebra concatenates direct-field singletons and completed child sequences in constructor-field order. Both computations therefore produce the same sequence. The two machines need not have the same intermediate demand order: the cursor yields during descent, whereas the eager fold applies its algebra after recursive children have completed. □

A client profile records the requested result, whether it needs local replacement or resumption, and whether forward observations require a productivity certificate. Profiles describe one-shot observation, resumable cursor interaction, or a finite batch; batch profiles request no cursor operations. The artifact’s policy client supports the batch result ordered-elements. For this comparison, the profile supplies exact constructor and element counts NN and MM (Equation (4)), for example from a maintained index or earlier analysis. The selector never traverses a root to obtain them. It first eliminates plans that lack required capabilities. It chooses root rescan for a one-shot observation and the persistent cursor for edits or resumable productive observations. For the declared ordered-elements batch, Lemma B.1 justifies comparing 2N+M2N + M and 3N3N: the cursor is selected when M<NM < N, and the eager fold otherwise.

Theorem B.2 (Contract-directed plan selection). For an accepted description and a profile satisfying the preconditions of some plan with the requested capabilities, the selector returns a plan with every requested capability. For an ordered-elements batch profile with supplied exact NN and MM, its selected plan has a reported control count no larger than that of the other batch plan.

Proof. The composition metadata is assembled from public operation clauses, so its capabilities are exactly those supplied by the generated interface. Lemma B.1 gives the common result semantics. Theorem 7.4 establishes 2N+M2N + M and Theorem C.1 establishes 3N3N for a completed eager fold. Comparing the two is equivalent to comparing MM with NN. The other cases are capability exclusions: root rescan has no saved focus, while the fold backend exposes neither cursor replacement nor cursor resumption. □

Batch measurements

We test the selector on a chain constructor with η\eta direct element fields, η∈{0,1,2,4,8}\eta\in\{0, 1, 2, 4, 8\}, and 4,096 links, so N=4,097N = 4{,}097 and M=4,096ηM = 4{,}096\eta. Every policy builds and consumes the same ordered element list. Comparing 2N+M2N + M with 3N3N selects the faster of the cursor and the unbounded eager fold at all five tested densities: the cursor is 2.9 times faster at η=1\eta= 1, and the fold 2.1 times faster at η=2\eta= 2. At η=1\eta= 1 the counts differ by one transition, so this agreement does not show that the count margin predicts the time margin. Table 3 reports the measurements.

η\etaSelected planCursorFoldFold, fuel 31Recursive
0Cursor20.240.254.95.3
1Cursor52.5152.6150.089.7
2Fold252.4120.5236.0180.6
4Fold331.8180.7222.9191.2
8Fold620.8307.0324.3223.3

Table 3. Common-output batch traversal: median μ\mus per tree. The count selector compares the generated cursor with the unbounded eager fold. Fuelled folds and direct recursion are additional baselines.

Each chain constructor places its η\eta direct element fields before its recursive child. The timed observer consumes every cell and value of the output list, so fold algebra and output construction are included. Exact list comparisons precede timing. Each of seven fresh-process samples uses 64 preconstructed roots; roots with η>0\eta> 0 have distinct element seeds. Roots with η=0\eta= 0 may share, and serve only as an empty-output control.

The unbounded fold is faster than the fuel-31 fold at every density except η=1\eta= 1, where the medians differ by 2% and the ranges overlap. Control counts alone do not determine elapsed time: the fold’s count is 3N3N at every density, while its time ranges from 40.2 to 307.0 μ\mus. Direct recursion is faster than both generated plans at η=0\eta= 0 and η=8\eta= 8 but provides neither generated cursor navigation nor the fold’s suspension interface.

The batch timings depend on GHC inlining: at η=1\eta= 1 GHC inlines next into the enumeration loop, which allocates 104 bytes per element, while at η=2\eta= 2 next remains a call and the loop allocates 168. Allocation in the timed region then grows from 27 MB, within one -A32m nursery, to 88 MB, so the cursor’s 4.8-fold slowdown between these densities reflects inlining and collection as well as element count.

Eager-fold construction, proof, and measurements

The cursor backend preserves source subtrees because navigation can revisit them. A fold instead replaces each completed child by a result. This change affects the frame payloads and the continuation clauses, while leaving the history representation intact. For one sort, an algebra α:Φ(X,J)→J\alpha: \Phi(X,J) \to J determines the catamorphism cata⁡α:T→J\operatorname{cata}\alpha: T \to J: recursively fold each child to a JJ, then apply α\alpha to that layer. For a family, the backend emits one indexed machine interface per root sort and an algebra family αi:Φi(X,J,…,J)→J\alpha_i : \Phi_i(X,J,\ldots,J) \to J. Kamot uses a common result type JJ across sorts. Each algebra processes one completed constructor layer.

Refining the recursive derivative

For left-to-right evaluation, a frame for recursive field ℓ\ell retains earlier recursive fields at type JJ, later ones at type TT, and nonrecursive fields at their original types:

Kfold(X,J,T)=∑c,ℓ:Ec,ℓ=Y(∏ℓ′<ℓEc,ℓ′[X,J])×(∏ℓ′>ℓEc,ℓ′[X,T]).(8)K_{\mathrm{fold}}(X,J,T) = \sum_{\substack{c,\ell:E_{c,\ell}=Y}} \left(\prod_{\ell'<\ell} E_{c,\ell'}[X,J]\right) \times\left(\prod_{\ell'>\ell} E_{c,\ell'}[X,T]\right). \tag*{(8)}

Here E[X,Z]E[X,Z] replaces the recursive variable by ZZ. Setting J=TJ = T recovers the ordinary recursive derivative. Keeping the two arguments distinct is the dissection refinement of McBride [23]; deriving a tail-recursive catamorphism this way is established prior work. Our backend specialises these records to the input constructors, attaching a cost and demand contract to each transition.

For Φ(X,Y)=X+Y×Y\Phi(X,Y) = X + Y \times Y, the two recursive positions give Kfold=T+JK_{\mathrm{fold}} = T + J: the first frame retains the right subtree while waiting for the left result, and the second retains the left result while waiting for the right. The path–trail correspondence applies to μQ.(1+Kfold×Q)\mu Q.(1 + K_{\mathrm{fold}} \times Q), representing the suspended ancestors by [Kfold][K_{\mathrm{fold}}] with the nearest frame exposed. Replacing a frame after completing a child takes constant structural work for fixed Φ\Phi.

For a family, a frame from parent sort ii to child sort jj retains earlier family children as results and later children as source values:

Kijfold(X,J,T)=∑c∈Ci, ℓ:Ec,ℓ=Yj(∏ℓ′<ℓEc,ℓ′[X,J])×(∏ℓ′>ℓEc,ℓ′[X,T]).K^{\mathrm{fold}}_{ij}(X,J,T)=\sum_{\substack{c\in C_i,\ \ell:E_{c,\ell}=Y_j}}\left(\prod_{\ell'<\ell}E_{c,\ell'}[X,J]\right)\times\left(\prod_{\ell'>\ell}E_{c,\ell'}[X,T]\right).

Here E[X,J]E[X,J] replaces every recursive sort by the common result type. The generated Haskell type indexes a frame by its parent and child sort and indexes a trail by its root and current sorts. GADT indices enforce the heterogeneous dissection invariant: a YjY_j return resumes only a frame awaiting its result, at the statically known parent sort.

One extension would give each sort its own result type JiJ_i, with algebras αi:Φi(X,J)→Ji\alpha_i:\Phi_i(X,J)\to J_i. An earlier child of sort jj would then contribute a JjJ_j, while a pending child would retain its source type TjT_j. For the lowered rose tree, Tree could produce JJ and List0 could produce ⟨J⟩\langle J\rangle, making the container-level algebra X×⟨J⟩→JX\times\langle J\rangle\to J directly expressible. The current backend uses a common JJ for all sorts; this extension would require corresponding changes to the generated layers, machine states, and correctness argument.

Evaluation strategy

The reference fold first exposes the current source constructor. It then recursively evaluates its YY fields in declaration order, forcing each child result to weak head normal form. Finally it applies α\alpha to the completed layer and forces its value to weak head normal form. Element and constant fields are carried unchanged; the algebra may demand them. Weak head normal form exposes the result’s outer constructor or function closure, not necessarily its contents.

The target has four states: descending into a source subtree, applying an algebra to a completed layer, returning a child result to a frame, and finishing at the root. At descent, it enters the first recursive field and saves a frame; when no field remains, it exposes an algebra request. On a child return, it either enters the next child with an updated frame or exposes the completed layer. Each transition is a nonrecursive, constructor-specialised clause. A shared tail-recursive driver invokes those clauses and forces each successor state; saved source fields remain lazy.

Suspension and operation contracts

The generated interface provides start, step, pending, runFor, and run. start saves the source without inspecting it; step executes one transition, leaving a finished state unchanged, and run drives the machine to completion. The operation runFor executes at most its positive fuel budget and returns either a completed result or a resumable state with the fuel consumed. pending exposes an algebra request without invoking the callback. A suspended state may be retained and resumed more than once with the same pure algebra.

The contracts distinguish descent, which demands the current outer constructor; application, which forces only the algebra result to weak head normal form; and return, which demands neither source nor algebra. Each has bounded structural overhead for a fixed description. Source-thunk evaluation and client-algebra work are charged separately, so one transition cannot interrupt a diverging thunk or callback. The JSON records this separation and the frame layouts; it is explanatory metadata, not an independently checked proof object.

Theorem C.1 (Indexed family fold and transition budget). For a finite value of any accepted family root with NN constructor occurrences across all family sorts, suppose every constructor demand and algebra evaluation required by the reference eager fold terminates. The emitted machine returns the same result and has the same ordered constructor demands and algebra applications. From start to Finished, it executes exactly 3N3N transitions: NN descents, NN applications, and NN returns. Its structural

overhead is OΦ(N)O_{\Phi}(N), excluding source forcing and algebra work. Partitioning the execution into positive fuel budgets preserves its result and total transition count. Each live history contains one frame per suspended ancestor.

Proof. Represent each pending reference call by its parent sort, constructor, active child sort and field, completed results, and unvisited fields. The single-sort Equation (8), or its indexed family form above, gives exactly this record. Relate the reference call stack to its backward trail in the same ancestor order; Theorem 4.2 ensures that the sort indices compose. Descent saves the record for the first child. On a child return, the emitted clause either replaces that record with the one for the next child, or constructs the parent layer from all completed results. Application invokes the same algebra on that layer and forces its result to the same extent. A return with empty history completes the root. These cases preserve the stack relation and the order of source demands and algebra calls. Induction on the finite source proves agreement and termination.

Each constructor is entered once, its completed layer is applied once, and its result is returned once, including the root return. This gives 3N3N. A transition inspects and constructs only bounded-size records for fixed Φ\Phi. The driver executes at most the supplied positive fuel and then returns its current state without modifying it, so concatenating resumed chunks gives the same transition sequence. The stack invariant also gives the history bound. Retained subtrees and result payloads are not bounded by the number of control records.

For potentially infinite data, every finite execution prefix still has a finite history. A finite positive budget returns a suspension or a completed result whenever each demand and application it reaches terminates. This does not assert that the fold will ever finish or produce a useful result on an infinite input. For example, an infinite list admits arbitrarily long finite descent prefixes, but this eager fold never reaches its empty constructor. Corollary 8.1 gives finite observations for cursors; this eager fold has no such guarantee.

A lazy binary fold with branch algebra λx y. x\lambda x\,y.\,x can return from Branch (Leaf 42) undefined. Our eager fold enters the right child and fails to return. Preserving such short-circuiting, including sharing and the algebra’s demand for recursive results, requires another translation and correctness argument. Likewise, the explicit machine moves traversal continuations from the host call stack into heap records; it does not promise constant total memory, bounded callback stack use, or backwards navigation through results that the algebra has discarded.

Theorem C.2 (End-to-end compilation and contracts). For every accepted ordered family Φ\Phi, the compiler compile applied to Φ\Phi terminates and emits cursor and eager-fold code, whose types are the indexed schemas of § 4 and Appendix § 18, together with a contract report. The ordinary cursor operations satisfy their reported contracts in the relation of Appendix § 25.§ 1. For every finite total root on which the stated eager evaluation terminates, the completed fold run satisfies the reported 3N3N transition count, constructor-demand trace, and client-algebra trace. Any emitted cursor certificate has the finite-observation guarantee of Theorem 8.2, or the local special case in Appendix § 16.

Proof. The source description is finite, and each compilation pass enumerates only its constructors, field positions, and finite lowering closure. Theorem 6.1, Corollary 8.1, and Theorems 7.1, 7.2, 7.3, 7.4, 8.2, and A.1 establish the cursor clauses and their reports. Theorem C.1 establishes the indexed eager-fold code, its transition count, and its traces. The generated types are the indexed derivative, trail, and refined-frame schemas used in those results; GHC acceptance of the emitted modules is tested, not proved.

Eager-fold validation

The fold suite of Appendix § 21.§ 1 also tests boundary suspension, undefined fields, a 10,000-transition prefix, and a four-recursive-field datatype.

With GHC optimisation disabled (-O0), a depth-200,000 skew binary tree completes under a 1 MiB stack limit with unbounded and 257-transition drivers. It has 400,001 constructors, executes 1,200,003 transitions, and sums 200,001 unit leaves. This tests control-stack safety for this scalar algebra, not arbitrary client code or allocation. Appendix § 18.§ 5 gives supplementary runtime comparisons against handwritten and recursive folds.

Supplementary eager-fold measurements

The fold experiment compares four implementations of annotation summation on a fully constructed depth-4,096 skewed syntax tree (8,193 constructors). The generated fold runs unbounded or in 31-transition budgets; baselines are a handwritten stack and direct recursion. A difference-list check instantiates Lemma B.1 for ordered-elements.

Table 4 gives the medians. Direct recursion is fastest on this finite, available input. The unbounded generated fold, a top-level loop over step that GHC specialises to the datatype, takes 216 μ\mus, within 4% of the handwritten stack’s 209 μ\mus, but allocates 671 KiB rather than 512 KiB. Running it in 31-transition budgets costs 238 μ\mus and 894 KiB. The generated machine provides suspension at higher allocation than either baseline.

Policyμ\mus/treeKiB/tree
Kamot eager fold216671
Kamot fold, fuel 31238894
Handwritten explicit stack209512
Direct recursive fold173160

Table 4. Finite eager-fold batch: annotation sum over a depth-4,096 skew syntax tree. Time and allocation are medians per tree.

Demand-admission measurements

The admission study uses the syntax family from Appendix § 21.§ 5. Each input contains a Let, a binding, a chain of App nodes, and a final expression. The local workload samples eight positions in chains of depth zero to three; the deep-local workload samples eight positions in a depth-96 chain; and the long-return workload starts at the deepest leaf in chains of depth 24–128. The next label in the last case lies beyond pending argument lists, whose constructors must be demanded on return.

A pure, non-inlined producer performs 128 fixed Word64 mixing iterations before exposing each constructor; its children remain lazy. Preparing the initial cursor and its old prefix is outside timing. An instrumented build checks that preparation demands exactly the prefix predicted by the independent source interpreter, and that subsequent entry events correspond to fresh producer calls. The timed executable has no producer instrumentation. This models a source with nontrivial production cost, not a measured parser or I/O system.

Fuelled checks transition and demand credits before each step. Certified starts a move only if its emitted bounds fit both credits, using the terminal suffix’s bound when the move has no return outcome and the depth bound otherwise. Defer skips the first window; direct ignores both credits. All survivors use the same fuelled driver. Three workloads cover shallow local queries, cheap deep queries, and long returns through child lists. Across budgets and cancellation rates, we measure 108 configurations checking answers, budgets, and demands against independent traces.

The application generates an admission helper from the emitted JSON. The terminal suffixes of App, Bind, and Let can only yield; their work/demand bounds are (2, 1), (2, 1), and (4, 2) respectively. The suffix of Lit returns, so the helper uses the family bound (5+3h,2+2h)(5 + 3h, 2 + 2h). It inspects only available terminal tags and cached depth, and rejects arithmetic overflow. Neither measured costs nor oracle traces are inputs to admission. An initial run used only the family bound; both runs and their exact generated sources are retained.

We cross three budget pairs, (64, 8), (256, 32), and (512, 256), with cancellation rates 0%, 50%, and 100%, three workloads, and four policies. Demand credits are the tighter admission constraint in this study. The rate selects query identifiers by (37id+11) mod 100<rate(37id + 11) \mathbin{\bmod} 100 < rate, independently of policy. An edit callback after the first window cancels only a query still unfinished; answers already delivered remain useful. The direct control may delay that callback by overrunning its quotas. A deferred survivor retries with the same unboxed driver as a fuelled survivor. Callback bookkeeping is measured, but the callback performs no other foreground computation.

The application is built with GHC 9.12.1 at -O2, without -threaded, and runs with +RTS -T -A32m on the machine of § 10. Seven fresh processes measure each configuration, rotating the order and retaining every sample. A throughput process runs 256 queries without per-window clocks or event logs; separate processes time 64 queries window by window. The artifact records 756 throughput samples, 78,533 windows, and 648 summary rows. Its validator recomputes all counters and window traces from the source interpreter, checks source hashes and regeneration, and reproduces every summary. An instrumented check covers all 108 configurations, zero-fuel non-strictness, and a bottom source that remains unforced after demand credits run out.

For the small-budget, 50%-cancellation long-return case, fuelled service takes 9.20–9.73 μ\mus per submitted query and certified admission takes 8.38–9.11 μ\mus. Both deliver the same 128 answers. Their total demands are 10,760 and 9,736: the difference is exactly the 1,024 discarded producer calls. Direct search delivers all 256 answers but exceeds the quota in every first window. Deferring everything matches certified admission on this workload but loses half of the local answers. Fuelled and certified admission answer all 256 local queries. At 32 demand credits, the terminal-suffix bound recovers 93 deep-local answers lost when admission uses only depth. On long returns with budgets (256, 32), certified admission saves 3,616 discarded evaluations but loses 15 answers that fuelled search completes; at (512, 256) it loses 13.

The no-cancellation control exposes the cost of waiting. On the same long-return inputs at budget (64, 8), every policy produces all 256 answers and demands all 19,200 constructors. Certified admission adds 256 callbacks and allocates 32,571 bytes per query, against 31,925 for fuelled execution; their timing ranges overlap. With 50% cancellation at larger budgets, Table 5 reports useful answers lost through conservative deferral. The 1 μs1\ \mu\mathrm{s} clock is too coarse to resolve submicrosecond local windows. Allocation measures total service allocation, not retained space, and no structural bound here is a wall-clock guarantee.

WorkDemandPolicyAnswersWastedμ\musbytes
648Fuelled1281,0249.5418,151
648Certified12808.7716,841
25632Fuelled1433,61612.0822,018
25632Certified12808.5516,007
512256Fuelled256016.5230,077
512256Certified243014.4827,605

Table 5. Admission on 256 long-return queries; 50% of unfinished queries are cancelled after the first window. Work and Demand are per-window transition and constructor credits; Wasted counts constructor evaluations for cancelled queries. Time and allocation are medians per submitted query, including cancelled queries.

Scheduling measurements

The scheduling study compares three policies with budget β=128\beta= 128 transitions on preconstructed rose trees. Direct search runs each move to its yield; fuelled search always runs a fuelled slice; contract-directed search runs the move directly when its certified bound bd(h)b_d(h) is at most β\beta and runs a fuelled slice otherwise (Corollary 8.5). Its three inputs expose different costs. The balanced four-way tree of depth six has 5,461 labels and short moves. The deep-return tree places a chain of 8,193 labelled nodes before a sibling, producing a long return through saved frames. The sparse variant adds a label-free constructor; 64 labelled subtrees each sit behind 256 silent nodes, and its prefix cycle receives no certificate.

Throughput samples scan 64 roots with distinct label seeds; separate fresh processes time individual scheduler slices. There are seven samples per workload and policy, with rotating policy order and the GHC/RTS configuration of § 10. Checks compare outputs and complete transition counts before timing and verify every certified bound and fuel limit. The experiment measures a cooperative scanning kernel, not end-to-end editor response time. Table 6 reports the results.

InputPolicyns/labelbytes/labelMax stepsMax slice
BalancedDirect66.8895464
Fuelled68.5919462
Contract-directed66.8895463
Deep returnDirect123.889532,774356
Fuelled130.89201285
Contract-directed127.59201283
SparseDirect17,030178,1891,54220
Fuelled17,663178,4971284
Contract-directed18,657178,4971286

Table 6. Family-cursor scheduling. Time and allocation are medians per label. The final column is the median of seven per-process maximum slice durations, in μs\mu\mathrm{s}. Maximum step counts are deterministic.

On the deep-return input, the seven per-process maxima range from 325 to 857 μs\mu\mathrm{s} for direct search and from 3 to 19 μs\mu\mathrm{s} for contract-directed search. The throughput ranges of the direct, fuelled, and contract-directed policies overlap: 111.8–134.9, 115.3–155.4, and 118.4–146.9 ns per label. On the balanced input the ranges are 63.3–69.8, 67.6–74.6, and 64.7–69.9 ns. The depth bound is conservative, so many individually cheap moves on the deep tree also take the fuelled path. A direct move avoids the fuelled driver’s boxed slice result, which saves 24 bytes per slice, or 2.6% of allocation on the balanced input. The admission study uses an unboxed driver, so its avoided source production does not depend on that overhead. The observed clock quantum is 1 μs1\ \mu\mathrm{s}, so small differences between shallow slice maxima are not meaningful. Allocation is measured, but collection counts and pauses are not; maximum slice times may include collections.

Additional measurements

Clause counts and validation coverage

For the precision study, an independent checker validates each productive divergence witness. Fields that the divergent search should never visit hold sentinel bottoms, so a search that takes wrong path fails. Replacing the sentinels with finite values gives fully productive inputs on which the first 20,000 transitions are unchanged. Divergence follows from the prefix-cycle argument; the finite traces test the implementation of each witness.

Nine descriptions generate ordinary and instrumented modules, checked with GHC 9.12.1 using warnings as errors. The cursor and cost suites cover 4,978 finite values (including 1,188 with mixed fields) and 28,482 positions. The fold suite checks 5,063 finite inputs against independent recursive specifications, the 3N3N count, all transition kinds, and budgets 1, 2, 7, and 31; Appendix § 18.§ 4 gives its further tests.

Table 7 lists measured clause counts for complete traversals of four inputs; each satisfies q=2N+Mq = 2N + M (Equation (4)). Its Largest search column ranges over initial entry and all moves, including the final boundary request. The sparse tree is Split (Item 0) (Split e (Item 1)) over the Sparse type of § 7, where e is a complete tree of Empty and Split nodes of height 10. One move takes 4,098 clauses; the value fails the local entry condition (Appendix § 16).

InputNNMMTotal qqLargest search
Log, 1,000 events1,0011,0003,0021,003
Balanced syntax, height 91,0231,0233,06911
Skewed syntax, 512 applications1,0251,0253,0754
Sparse tree, empty height 102,05124,1044,098

Table 7. Measured abstract clause counts for complete forward traversals. Every row satisfies q=2N+Mq = 2N + M. These are deterministic structural counts, not time measurements.

Replay and correction of a lazy event log

An event log may have a finite observed past and an unbounded future:

data Log a = End | Event Integer a (Log a)

The integer is an opaque timestamp and a is the editable payload. Differentiation gives a frame containing the timestamp and old payload, and a terminal record containing the timestamp and future log. The constructor is forward entry-guarded. Opening a nonempty log yields its payload without forcing the tail; each successful forward move inspects only the next event constructor. Successful adjacent moves have constant structural cost for this datatype. The history permits replay backwards and correction of one observed payload.

The streaming repair workload opens the first event, makes 2,048 forward requests, corrects every 64th payload, and retains the cursor for backward replay. A separate application test replaces event 999 and closes the edited cursor. The checks establish persistence, replay, and prefix repair; opening Event 0 0 undefined leaves the suffix unforced. The generated machine executes 4,097 clauses: one entry and two per successful forward move. We compare it with a productive traversal-based generic zipper and root rescan; timing covers advancing, repairing, and closing the prefix.

Table 8 gives seven-sample medians in the configuration of § 10. The generated cursor is six times faster than the generic zipper and allocates under one quarter as much per request; rescan has no replayable history and is about 114 times slower. The dissection port is evaluated on the finite annotation workload, because it has no packaged coinductive frontend.

Policyns/requestbytes/requestlive KiB
Kamot cursor25247202
External zippers1521,216919
Direct recursive rescan2,8391,332170

Table 8. Infinite streaming repair: 2,048 forward requests and a repair every 64 requests. Time and allocation are per-request medians; separate live-heap runs observe the same 2,050-event prefix.

Incremental annotation service

The annotation-service kernel edits annotations attached to syntax nodes:

data Expr a
  = Var a Int
  | Lit a Integer
  | App a (Expr a) (Expr a)
  | Lam a Char (Expr a)

The focus is an annotation, not an arbitrary subtree. Every recursive constructor begins with an annotation, so forward traversal satisfies the local entry condition of Theorem A.1 with f=2f = 2. A move from depth hh consequently uses at most 5(h+1)+15(h + 1) + 1 search clauses. This applies even to an incrementally unfolded infinite syntax value, provided its demanded constructors are productive. A client can visit and update available annotations without forcing a variable identifier, literal, or unvisited sibling.

Tests cover balanced and skewed trees, finite reconstruction, undefined unvisited fields, and a thousand moves through an infinite annotated unfolding. The incremental annotation-service kernel answers 2,048 successive “next annotation” requests and persists an edit every 64 requests. Its standalone selector is the one of Appendix § 17; for this profile, productive local replacement, it selects the persistent cursor.

On a skewed syntax value of depth 4,096, the selected cursor executes 4,097 search clauses; restart executes 4,196,352. Both return the same annotations, and the cursor reconstructs the edited root. Thus the generated contract justifies retaining the typed continuation for sequential interaction with local edits.

Runtime and allocation comparison

We measured this service on a fully constructed depth-4,096 skewed syntax tree. Table 2 reports seven-sample medians in the -threaded configuration of § 10. Allocation is the RTS allocated_bytes delta; each timing sample runs in a fresh process. The experiments use no core pinning or frequency control. Samples run 16 roots for recursive rescan, 64 for each generic baseline, and 256 for the generated cursor and handwritten stack. Reported ranges describe fresh-process variation, not confidence intervals. Times are whole-session measurements divided by request count, not individual request latencies. The dissection harness also converts the completed polynomial representation back to the native tree inside the measured interval; its initial conversion is outside that interval. Timings include navigation, reconstruction, and output conversion.

A separate run of seven fresh-process samples on 64 preconstructed roots stops the dissection session after navigation and edits, after reconstruction and observation of the polynomial result, or after conversion to the native tree. The table reports per-request medians and timing ranges.

Stopping pointns/requestRangebytes/request
Navigation and edits270252–329482
Polynomial result613591–628850
Native tree604555–6691,058

Table 2 (PDF p. 31).

Conversion adds 208 bytes per request. Its time cost cannot be isolated: the difference between the two longer modes lies within run-to-run variation, and the two modes observe different trees. Navigation and edits alone take 2.5 times the generated cursor’s complete session time.

Heap snapshots use separate fresh processes. For finite inputs, every policy fully observes the source and reconstructed output before collection. A snapshot retains one cursor or edited root; it reports total live heap, including reachable source data. Stream snapshots materialise and observe exactly 2,050 events; stream timing starts with only the first event ready. All stream policies use the same source datatype.

Exact-output checks precede measurement, and a test with an undefined stream tail detects demand beyond the observed prefix. The artifact records all samples, their ranges, source hashes, and build and runtime settings.

The generated cursor has similar amortised time per request to the handwritten stack (107 versus 113 ns) while allocating 24% fewer bytes. In this harness, it is 5.2× faster than the generic-dissection port and uses about 19% of its allocation; against Jacket/Path, it is 6.4× faster and uses about 5% of its allocation. Root rescan is 46× slower and allocates 95× more per request. Retaining the generated cursor costs about 32 KiB more live heap than retaining the rescan root in each workload.

Syntax-service family kernel

The family

data Expr a = Lit a | App a (Expr a) [Expr a] | Let a [Decl a] (Expr a)
data Decl a = Bind a (Expr a)

lowers its argument and binding lists to auxiliary sorts. Forward moves are certified with at most 5+3h5 + 3h transitions and 2+2h2 + 2h constructor demands; backward moves are unknown. The session makes 2,048 next requests from the first annotation, replaces every 64th selected annotation, then closes and observes the rebuilt root. The mixed input interleaves applications and lets and has 23,206 annotations; the deep input is a chain of 2,048 lets with 6,145 annotations. Two handwritten machines use the same lowered source types. The indexed machine has independently written GADT frames, navigation, and reconstruction, with non-strict payloads matching the generated cursor. The unindexed machine has a sum-of-sorts representation, dynamic sort checks, and strict payload fields. Rescan searches from the root for every request. Every policy’s output matches an independent preorder oracle before timing. Each input and policy has seven fresh-process samples with rotating order, over 256 roots per process for all four policies.

Generated and handwritten indexed cursors have identical per-request allocation (Table 9). Their timing ranges overlap on both inputs: 77–83 versus 78–85 ns on the mixed tree, and 56–59 versus 55–58 ns on the let chain. The unindexed machine is faster on the let chain but allocates more; these differences depend on its representation. The artifact also retains an earlier three-policy run, whose samples are not pooled with these. Additional checks cover 36 small roots at every request count, final boundaries, partial payloads, and an infinite prefix; these are correctness checks, not timing inputs.

PolicyMixed nsMixed bytesDeep let chain nsDeep let chain bytes
KAMOT family cursor7824658253
Handwritten indexed stack7824656253
Handwritten unindexed stack8735738309
Rescan3,75716,3843,39611,308

Table 9. Syntax-service family kernel: medians per request.

Code size and compile time

Across 12 one-sort descriptions varying constructor count and recursive-field arity, generated Haskell ranges from 1.9 KiB (87 ms to check) to 30.3 KiB (159 ms).

The scaling run covers the 19 corpus datatypes after container lowering (1–10 sorts, 2–21 constructors) and the 81 generated families of § 10.1 (1–3 sorts, 3–15 constructors). Cursor modules range from 2.9 to 29.0 KiB, resumable cursor modules from 6.2 to 45.6 KiB, and fold modules from 3.0 to 18.8 KiB. A least-squares fit of cursor size against active fields gives about 1.8 KiB plus 0.6 KiB per active field (R2=0.96R^2 = 0.96); constructor count alone fits less well (R2=0.81R^2 = 0.81). GHC -fno-code takes 87–149 ms per cursor module and 98–175 ms per fold module, including the source module it imports. The largest module comes from the located Haskell-module datatype (10 sorts, 21 constructors).

These corpus fits do not establish an asymptotic scaling law. A second study uses rings of 1, 4, 16, and 32 mutually recursive sorts, with a labelled leaf and a labelled binary constructor per sort. Two further cases independently increase constructor count or recursive-field arity. Every measurement is a fresh GHC invocation with a fresh output directory and -fforce-recomp; we report medians of three samples. Cursor modules range from 3.8 to 221.6 KiB and take 0.16–2.76 s to compile with -O2. Fold builds, including their generated source module and runtime dependency, take 0.27–3.46 s. The rise in cursor size reflects reconstruction helpers repeated for each root sort, as accounted for in § 5. The 32-sort fold exceeds GHC’s default pattern-checking model budget of 30; the complete study uses -fmax-pmcheck-models=256 throughout, with -Wall -Werror. The initial failed run is retained in the artifact. This is a controlled build-cost study, not evidence about whole-program optimisation or runtime.

Proof of compositional family contracts

Lemma G.1 (Empty returns witness nullability). If a reference run enters a value tt of sort ii and later returns from tt without an intervening yield, then Null⁡(i)\operatorname{Null}(i).

Proof. The run between the entry and the return is finite. It leaves each node it enters only after scanning all of that node’s active fields, and it does not yield, so no entered node has an XX field and every YY field of an entered node is itself entered and returned from. The entered nodes form a finite tree rooted at tt. Induction on its height, applying the nullability rule at each node, shows that every entered sort, in particular ii, is nullable. Constant fields are never entered, so they may hold any value. □

Lemma G.2 (Suffix summary soundness). Let uu be any ordered suffix of a constructor’s fields with a bounded summary S(u)S(u), and assume demanded roots are productive. Suppose every entry summary consulted in computing S(u)S(u) is sound under this assumption: entering any value of its sort reaches a yield or a pending return within the corresponding outcome bound, and cannot take an omitted outcome. Starting the scan at uu, with any well-sorted field values and stack, reaches a yield or the surrounding constructor’s pending return within the corresponding bound of S(u)S(u). The bound excludes the control action that starts the scan. No condition is imposed on the fields preceding uu.

Proof. Induct on the length of uu. The empty suffix returns and an element field yields, each with cost (0,0)(0, 0); skipping a constant changes neither cost nor outcome. For u=Yju′u = Y_j u', soundness of Ej\mathcal{E}_j gives two possibilities. A child yield ends the scan within Ej.yield\mathcal{E}_j.\mathrm{yield}. A child return costs at most Ej.return\mathcal{E}_j.\mathrm{return} before its pending return action; that action costs (1,0)(1, 0) and resumes at u′u', with induction hypothesis applies. These are exactly the alternatives in the rules for S(Yju′)S(Y_j u'). An omitted child outcome cannot occur, so an alternative that uses it need not be bounded. If an alternative uses no omitted child outcome, every summary needed for u′u' was consulted in computing S(u)S(u), so the induction hypothesis applies. Componentwise maximum bounds either yield alternative, and addition bounds the return alternative. Thus omitted suffix outcomes cannot occur either.

Proof of Theorem 8.2. Write ⊏\sqsubset for the order in which bounded entry summaries are evaluated, so Ei\mathcal{E}_i depends only on summaries Ej\mathcal{E}_j with i→dji \mathrel{\to_d} j and j⊏ij \sqsubset i. A sort without constructors has no values, and both of its outcomes are impossible.

Claim A. Let Ei\mathcal{E}_i be bounded, tt a finite or infinite value of sort ii, and κ\kappa any well-sorted stack. The run from Enter⁡d(t,κ)\operatorname{Enter}_d(t,\kappa) reaches either a Yield within Ei.yield\mathcal{E}_i.\mathrm{yield} or the configuration Return⁡d(t,κ)\operatorname{Return}_d(t,\kappa) within Ei.return\mathcal{E}_i.\mathrm{return}, counting transitions and constructor demands, and only an outcome that Ei\mathcal{E}_i marks possible occurs.

We prove Claim A by induction on ⊏\sqsubset. Let t=c(v)t=c(v). The entry step matches cc and costs (1,1)(1,1). For the scan of cc’s fields we prove Claim B: for each suffix uu of the fields of cc in direction dd that the scan can reach without yielding, it reaches a Yield within S(u).yieldS(u).\mathrm{yield} or the end of cc within S(u).returnS(u).\mathrm{return}.

We induct on the length of uu. The empty, element, and constant cases are as in the proof of Lemma G.2. Suppose u=Yju′u=Y_j u'. The scan reached this field without yielding, so every earlier active field of cc is a YY field whose child returned empty, and by Lemma G.1 each of those sorts is nullable. The edge rule therefore gives i→dji \mathrel{\to_d} j, so j⊏ij \sqsubset i and Claim A holds for the child t′t' of sort jj.

The child segment either yields within Ej.yield\mathcal{E}_j.\mathrm{yield}, which ends the scan, or reaches its pending return within Ej.return\mathcal{E}_j.\mathrm{return}. In the latter case the return step costs (1,0)(1,0), demands nothing, and resumes the scan at u′u', where the induction hypothesis applies. This is the rule of § 8.1 for S(Yju′)S(Y_j u'). An outcome marked impossible cannot occur, because each of its alternatives contains an impossible child outcome or an impossible suffix outcome. Adding the entry cost and maximising over constructors gives Ei\mathcal{E}_i. The child t′t' may be infinite or contain elements: then it cannot return empty, by the proof of Lemma G.1, and Claim A bounds its segment up to its first yield.

Moves. By Lemma K.2, a valid cursor at depth hh encodes a yield whose stack holds hh records. A move from a cursor whose terminal context records constructor cc and position ℓ\ell performs one advance step and scans the fields after ℓ\ell. This suffix need not be reachable from constructor entry before a yield, so Claim B alone does not apply. The emitted move certificate requires bounded summaries for every terminal and frame suffix. Claim A has established soundness of every entry summary they consult, so Lemma G.2 applies at each of these starting positions. Adding the advance action gives the terminal bound (wB,nB)(w_B,n_B). If this segment reaches the pending return from cc, returning through the nearest frame starts its suffix; including that return action gives (wK,nK)(w_K,n_K). Each frame segment starts by popping one frame off the original stack. Any child entered within that segment either yields or returns before the segment ends, so an exhausted segment leaves no new frames. Hence at most hh such frame segments run, and the final root return to End costs one further step with no demand. Summing gives bd(h)=wB+hwK+1b_d(h)=w_B+h w_K+1 and nB+hnKn_B+h n_K. Entry is Claim A at the root with the same final step.

Each step demands at most one outer constructor, which a productive root supplies in finite time, so a bounded number of steps takes finite time. Lemma K.1 maps each reference step to one generated clause with the same demand, which transfers the bounds to the generated searches.

Rose-tree refinement. For a focus in a value of sort Tree, each of its δ\delta ancestors contributes one Frame_Tree_Node_1 and one Frame_List0_List0Cons_0. Each earlier sibling contributes one Frame_List0_List0Cons_1, so h=2δ+sh=2\delta+s for ss such siblings. Their return outcomes are (1,0)(1,0), (3,1)(3,1), and (1,0)(1,0), respectively; the terminal return outcome is (3,1)(3,1). If every segment returns, the move costs at most (4+4δ+s,1+δ)(4+4\delta+s,1+\delta), including the final root return. A yielding segment replaces its return outcome (3,1)(3, 1) by (3,2)(3, 2) and skips the remaining frames and root return. Thus every move is bounded by (4+4δ+s,2+δ)(4 + 4\delta+ s, 2 + \delta): only the demand bound depends solely on source depth; the work bound also counts earlier siblings.

Proof of completeness

Throughout, the family is inhabited and accepted, and dd is fixed. By Lemma K.1 it suffices to count reference steps.

Lemma H.1 (Element-free values). For every nullable sort jj there is a finite value zjz_j of sort jj that contains no element, and a run entering zjz_j returns from it after finitely many steps without yielding.

Proof. Induct on the derivation of Null⁡(j)\operatorname{Null}(j). Its last rule names a constructor with no XX field whose recursive fields have nullable sorts; fill those with the values given by induction and each constant field with a value of its type. The run scans every field of every node it enters, finds no element, and terminates because the value is finite. □

Lemma H.2 (Realising prefix edges). If i→dji \mathrel{\to_d} j, then for every value t′t' of sort jj there is a value tt of sort ii, finite apart from t′t', whose entry reaches t′t' after at least one step and without yielding.

Proof. The edge rule names a constructor cc of sort ii and a field ℓ\ell with Ec,ℓ=YjE_{c,\ell}=Y_j such that every active field before ℓ\ell in direction dd is a YY field of nullable sort. Let t=c(v)t=c(v) with vℓ=t′v_\ell=t', the element-free values of Lemma H.1 in the earlier active fields, any values in constant fields, and finite values in the later fields; these exist because every sort has a finite value. The run matches cc, skips constants, enters and returns from each earlier child without yielding, and then enters t′t'. □

Lemma H.3 (Pumping). If EjE_j is unknown, then for every nn there is a finite value tnt_n of sort jj such that a run entering tnt_n takes at least nn steps without yielding, and there is a productive infinite value t∞t_\infty of sort jj, whose constructors are all defined, on which a run entering it neither yields nor returns.

Proof. Entry summaries are evaluated while some sort has all its prefix successors evaluated. A sort left unknown therefore has a prefix successor that is also unknown. Since there are finitely many sorts, we can choose an infinite walk j=j0→dj1→d⋯j=j_0\mathrel{\to_d}j_1\mathrel{\to_d}\cdots consisting of a finite stem followed by a repeated cycle. Applying Lemma H.2 along its first nn edges, with any finite value at the end, gives tnt_n; each edge costs at least one step and no yield. Construct t∞t_\infty along the whole walk, including the stem, using the edge constructors and finite fillers from that lemma. Every constructor is defined. The run follows the infinite walk, so it neither yields nor returns from t∞t_\infty. □

Lemma H.4 (Reachability of finite contexts). Every well-sorted cursor whose reconstructed root has a finite, fully defined constructor tree is reached by entry and finitely many moves in direction dd on that root.

Proof. Fill the terminal hole with the focused element, then fill each frame’s recursive hole with the reconstructed child, nearest frame first. Each filling preserves its constructor’s field order and sort, yielding a finite root. Traversal of a finite child visits its elements and returns. Thus, at each ancestor of the focus, finitely many steps and advances traverse the fields preceding the chosen child in direction dd and enter it with exactly that ancestor’s frame saved. Induction down the path reaches the terminal constructor with the given trail. Traversing its preceding fields in direction dd then reaches the focus with the given terminal record. Grouping the steps between successive yields gives entry followed by completed public moves. □

Proof of Theorem 8.4. The forward implications of parts 1 and 2 follow from Theorem 8.2.

Part 1. If Er\mathcal{E}_r is unknown for a root sort rr, root entry on the value tnt_n of Lemma H.3 takes at least nn steps.

Part 2. Suppose no move certificate is emitted. Some terminal or frame suffix uu, following field ℓ\ell of a constructor cc of sort ii, then has an unknown summary. Thus uu contains a recursive field YjY_j with unknown Ej\mathcal{E}_j, preceded only by constants and nullable recursive fields. Because the family is inhabited, sort ii occurs at some node of a finite value of a root sort. Replace the subtree at that node by c(v)c(v), where vℓv_\ell is an element if uu is a terminal suffix and a finite value containing an element if uu is a frame suffix; the fields of uu before YjY_j hold element-free values, the field YjY_j holds tnt_n, and the remaining fields hold finite values. Fix the surrounding context and all finite fillers independently of nn. In the terminal case, place the cursor at vℓv_\ell. In the frame case, place it at the last element of vℓv_\ell in direction dd; its move returns from vℓv_\ell after finitely many steps and then runs the frame suffix uu.

Lemma H.4 ensures that entry and finitely many moves reach this cursor. No ancestor of its focus lies inside tnt_n, so its trail depth hh is fixed. Its next move crosses the element-free fields and enters tnt_n, taking at least nn steps. Each pumped edge enters a new constructor, so demands are unbounded too. Thus no function of hh bounds these moves, proving the reverse implication of part 2.

Part 3. Replace tnt_n by t∞t_\infty. The prefix reaching the cursor visits only its finite ancestors and the fields preceding the focus in direction dd; it never demands the replaced subtree. The same entry and moves reach the cursor on a productive infinite root; its next move diverges. □

Path–trail correspondence proof

Proof of Lemma 4.1. Setting. Write P=μQ.(B+L×Q×R)P = \mu Q.(B + L \times Q \times R) for the paths, with constructors Stop⁡(b)\operatorname{Stop}(b) and Step⁡(l,p,r)\operatorname{Step}(l,p,r), where b∈Bb \in B, l∈Ll \in L, p∈Pp \in P, and r∈Rr \in R. A history is a value of [L×R⟩[L \times R\rangle, built from BNil and Snoc. Paths are finite because PP is a least fixed point, and histories are finite by definition. The left-to-right order of a path’s fields is

fields⁡(Stop⁡(b))=b,fields⁡(Step⁡(l,p,r))=l,fields⁡(p),r.\operatorname{fields}(\operatorname{Stop}(b)) = b,\qquad\operatorname{fields}(\operatorname{Step}(l,p,r)) = l,\operatorname{fields}(p),r.

For steps (l1,r1),…,(ln,rn)(l_1,r_1),\ldots,(l_n,r_n), outermost first, and terminal bb, this is l1,…,ln,b,rn,…,r1l_1,\ldots,l_n,b,r_n,\ldots,r_1. From the definitions of § 4,

before⁡(Snoc⁡ H (l,r))=before⁡(H),l,after⁡(Snoc⁡ H (l,r))=r,after⁡(H),\operatorname{before}(\operatorname{Snoc}\ H\ (l,r)) = \operatorname{before}(H),l,\qquad\operatorname{after}(\operatorname{Snoc}\ H\ (l,r)) = r,\operatorname{after}(H),

and both are empty for BNil.

The map and its inverse. Define φ:P→[L×R⟩×B\varphi: P \to[L \times R\rangle\times B by φ(p)=down⁡(BNil⁡,p)\varphi(p) = \operatorname{down}(\operatorname{BNil},p), where

down⁡(H,Stop⁡(b))=(H,b),\operatorname{down}(H,\operatorname{Stop}(b)) = (H,b),
down⁡(H,Step⁡(l,p,r))=down⁡(Snoc⁡ H (l,r),p).\operatorname{down}(H,\operatorname{Step}(l,p,r)) = \operatorname{down}(\operatorname{Snoc}\ H\ (l,r),p).

Define ψ:[L×R⟩×B→P\psi: [L \times R\rangle\times B \to P by ψ(H,b)=up⁡(H,Stop⁡(b))\psi(H,b) = \operatorname{up}(H,\operatorname{Stop}(b)), where

up⁡(BNil⁡,p)=p,\operatorname{up}(\operatorname{BNil},p) = p,
up⁡(Snoc⁡ H (l,r),p)=up⁡(H,Step⁡(l,p,r)).\operatorname{up}(\operatorname{Snoc}\ H\ (l,r),p) = \operatorname{up}(H,\operatorname{Step}(l,p,r)).

One recursive call of down⁡\operatorname{down} is a transfer: it moves the outermost step of the residual path, with both its fields, onto the history. One recursive call of up⁡\operatorname{up} is the inverse transfer. The function down⁡\operatorname{down} recurses on a smaller path and up⁡\operatorname{up} on a smaller history, so both terminate.

Invariant. A state (H,p)(H,p) pairs a history with a residual path. Its reading is the sequence before⁡(H)\operatorname{before}(H), fields⁡(p)\operatorname{fields}(p), after⁡(H)\operatorname{after}(H). The states (H,Step⁡(l,p,r))(H,\operatorname{Step}(l,p,r)) and (Snoc⁡ H (l,r),p)(\operatorname{Snoc}\ H\ (l,r),p) both read as

before⁡(H),l,fields⁡(p),r,after⁡(H).\operatorname{before}(H),l,\operatorname{fields}(p),r,\operatorname{after}(H).

A transfer maps the first state to the second, and the inverse transfer maps the second to the first. Hence both preserve the reading.

Order preservation. Let φ(p)=(H,b)\varphi(p) = (H, b). The run of downdown starts in state (BNil,p)(\mathrm{BNil}, p), whose reading is fields(p)fields(p), and ends in state (H,Stop(b))(H, \mathrm{Stop}(b)), whose reading is before(H)before(H), bb, after(H)after(H). By the invariant the two readings are equal, which is the order-preservation property.

Mutual inverses. First, ψ(down(H,p))=up(H,p)\psi(down(H, p)) = up(H, p) for all HH and pp, by induction on pp. For p=Stop(b)p = \mathrm{Stop}(b), both sides equal up(H,Stop(b))up(H, \mathrm{Stop}(b)). For p=Step(l,p′,r)p = \mathrm{Step}(l, p', r),

ψ(down(H,p))=ψ(down(Snoc H (l,r),p′))=up(Snoc H (l,r),p′)=up(H,p),\psi(down(H, p)) = \psi(down(\mathrm{Snoc}\ H\ (l, r), p')) = up(\mathrm{Snoc}\ H\ (l, r), p') = up(H, p),

by the definitions of downdown and upup and the induction hypothesis. Taking H=BNilH = \mathrm{BNil} gives ψ(φ(p))=up(BNil,p)=p\psi(\varphi(p)) = up(\mathrm{BNil}, p) = p.

Second, φ(up(H,p))=down(H,p)\varphi(up(H, p)) = down(H, p) for all HH and pp, by induction on HH. For H=BNilH = \mathrm{BNil}, both sides equal down(BNil,p)down(\mathrm{BNil}, p). For H=Snoc H′ (l,r)H = \mathrm{Snoc}\ H'\ (l, r),

φ(up(H,p))=φ(up(H′,Step(l,p,r)))=down(H′,Step(l,p,r))=down(H,p).\varphi(up(H, p)) = \varphi(up(H', \mathrm{Step}(l, p, r))) = down(H', \mathrm{Step}(l, p, r)) = down(H, p).

Taking p=Stop(b)p = \mathrm{Stop}(b) gives φ(ψ(H,b))=down(H,Stop(b))=(H,b)\varphi(\psi(H, b)) = down(H, \mathrm{Stop}(b)) = (H, b). Hence φ\varphi is a bijection with inverse ψ\psi.

Cost. Costs are structural work in the model of § 7. A transfer matches one Step constructor, allocates one Snoc cell and one pair, and copies the references ll, pp, and rr. An inverse transfer matches one Snoc cell and its pair, allocates one Step cell, and copies the same three references. Each therefore takes constant structural work. On a path of nn steps, φ\varphi performs nn transfers and one final Stop match, which allocates the result pair. On a history of nn steps, ψ\psi allocates one Stop cell, performs nn inverse transfers, and ends with one BNil match. Each direction thus takes O(n+1)O(n + 1) structural work and allocates O(n+1)O(n + 1) spine cells.

No stored value is inspected. Every clause of downdown and upup matches only a path constructor, a history constructor, or a pair. The definitions are parametric in LL, RR, and BB: each stored ll, rr, or bb is bound to a variable and copied as a reference, so it is shared and never inspected. The bounds cover structural work on the finite spine, excluding the cost of exposing lazy source constructors. □\square

Contract semantics and lowering

Ordinary cursor contracts

A contract for operation oo is a record ⟨Wo,Do,Po,Go⟩\langle W_o, D_o, P_o, G_o \rangle: a work expression, a demand descriptor, the assumptions under which the contract holds, and an optional certificate bounding work and constructor demands. Work expressions are

W::=γ∣ξ∣W+W∣γ⋅ξ∣max⁡(W,W),W ::= \gamma\mid\xi\mid W + W \mid\gamma\cdot\xi\mid\max(W, W),

where γ\gamma is a natural constant and ξ∈{h,q,N,M,fuel}\xi\in\{h, q, N, M, \mathrm{fuel}\}. Ordinary cursor counts are exact; fuelled drivers instead report the upper bound max⁡(0,fuel)\max(0, \mathrm{fuel}) for a transition budget fuel\mathrm{fuel}. The fold backend reports 3N3N for a completed eager run and distinguishes constructor demands from client-algebra applications (Appendix § 18). The JSON reports represent work as an abstract syntax tree alongside a printed description, and also record assumptions, demand descriptions, and certificates. Demand descriptors are

D::=ϵ∣search(d)∣traverse(d)∣match∣algebra.D ::= \epsilon\mid\mathrm{search}(d) \mid\mathrm{traverse}(d) \mid\mathrm{match} \mid\mathrm{algebra}.

For cursor operations, ϵ\epsilon means no source demand, search(d)\mathrm{search}(d) records constructor matches up to the next yield or boundary in direction dd, and traverse(d)\mathrm{traverse}(d) records those of a complete traversal. The fold descriptors match and algebra distinguish source-constructor demands from client-algebra applications; their semantics are given in Appendix § 18. The relation below concerns ordinary cursors; resumable-driver bounds are stated in Corollary 8.5. Its result postconditions are the positional guarantees of § 6; PoP_o records the assumptions stated in § 7.

Label every reference and generated control step by either match⁡(c)\operatorname{match}(c), when it exposes source constructor cc, or ϵ\epsilon, otherwise. Write

⟨o,s⟩→w,δs′\langle o,s\rangle\xrightarrow{w,\delta} s'

for a finite prefix of ww generated control steps of oo from state ss, with source-label trace δ\delta, and write ⟨o,s⟩⇓w,δz\langle o,s\rangle\Downarrow^{w,\delta} z when such a prefix ends in public result zz. Cursor focus and replacement take zero control steps: their bounded record accesses are accounted for by the structural bound of Theorem 7.4.

Work and demand descriptors denote properties of the reference machine of Section 6, not of the generated run. The encoding of that section keeps every tag and stored field, so it is injective and a generated state can be decoded. By Lemma K.2, every valid cursor encodes a yield. For an operation oo and state ss, let Ro(s)R_o(s) be the reference run from the corresponding configuration: Enter⁡d(t,[ ])\operatorname{Enter}_d(t, [\ ]) for entry at root tt, and Advance⁡d\operatorname{Advance}_d of the decoded yield for a move. It stops at its first Yield or End and may be infinite. For traverse, Ro(s)R_o(s) is the complete reference traversal to End; focus, replace, and close run no search, and their Ro(s)R_o(s) is empty.

For a contract ⟨W,D,P,G⟩\langle W,D,P,G\rangle of oo, a natural-valued valuation ρ\rho agrees with ss when each of hh, NN, MM occurring in WW or GG is assigned its corresponding finite depth or count. If qq occurs and Ro(s)R_o(s) is finite, ρ(q)\rho(q) is its length; an infinite run imposes no condition on ρ(q)\rho(q). Unused variables impose no condition. Thus a local move requires no finite size for the surrounding input, whereas the complete-traversal contract requires finite NN and MM.

Write ⟦W⟧ρ\llbracket W\rrbracket_\rho for the value of WW under ρ\rho, using ordinary arithmetic and maximum. The descriptor ⟦search⁡(d)⟧(s)\llbracket\operatorname{search}(d)\rrbracket(s) is the label trace of Ro(s)R_o(s); traverse⁡(d)\operatorname{traverse}(d) denotes the trace of the complete reference traversal and ϵ\epsilon the empty trace. The judgement Φ,o⊨ρ⟨W,D,P,G⟩\Phi,o \models_\rho\langle W,D,P,G\rangle holds when every source state agreeing with ρ\rho and satisfying PP has all three properties below. An operation satisfies a contract when the judgement holds for every ρ\rho.

  1. Partial correctness. If ⟨o,s⟩⇓w,δz\langle o,s\rangle\Downarrow^{w,\delta} z, then Ro(s)R_o(s) is finite, w=⟦W⟧ρw=\llbracket W\rrbracket_\rho, δ=⟦D⟧(s)\delta=\llbracket D\rrbracket(s), and, for entry and moves, zz encodes the final configuration of Ro(s)R_o(s). Focus returns the selected element, replacement changes only that occurrence, and closing rebuilds the root.

  1. Prefix correspondence. For entry, moves, and complete traversal, the generated run and Ro(s)R_o(s) have prefixes of exactly the same finite lengths. Corresponding prefixes have the same labels and related configurations. Focus, replacement, and closing are not searches; their work and demand are specified by partial correctness above.

  1. Conditional termination. If GG is present and demanded roots are productive, Ro(s)R_o(s) is finite and its length and demand count satisfy the bounds of GG.

For an uncertified move, W=qW=q and D=search⁡(d)D=\operatorname{search}(d) thus assert that the generated search has the length, trace, and result of the reference search; they assert no bound on that length, and a diverging search has exactly the finite prefixes of a diverging reference run. The relation abstracts away from the time to expose a demanded source constructor and from client-algebra work.

Proof of Theorems 7.1, 7.2, and 7.3. Lemma K.2 and Theorem 4.2 supply the representation of every valid cursor. For entry (Theorem 7.1) and moves (Theorem 7.2), Lemma K.1 relates one labelled reference step to one emitted clause. Induction on prefix length proves prefix correspondence, including divergent runs. A terminating prefix gives W=qW=q, the reference demand trace, and the corresponding result. Concatenating the entry prefix and the successive move prefixes gives the complete-traversal correspondence; Theorem 7.4 gives its 2N+M2N+M count. For Theorem 7.3, focus and replacement take zero control steps and inspect no source constructor. Closing takes h+1h+1 counted steps without source demand, as in the proof of Theorem 7.4. These three operations therefore satisfy partial correctness with their empty reference searches. Theorem 8.2 supplies conditional termination and the reported bounds. These cases cover every row of the emitted report. □

Container lowering

The frontend of § 3 lowers each accepted list, Maybe, Either, or declared unary container application to a memoised auxiliary sort. The first occurrence of [τ][\tau], Maybe τ\tau, Either τ1\tau_1 τ2\tau_2, or U τU\ \tau receives a fresh sort whose ordered regular body is recursively lowered; equal applications reuse it. Within a declared unary container, the internal name Self denotes its recursive occurrence at the unchanged parameter and becomes the fresh sort. The set of applications reached this way is the lowering closure; § 3 requires it to be finite.

The source declaration has its own signature Σ\Sigma. Its sorts are the declared types and the container applications in the finite closure, such as [Tree a][\mathrm{Tree}\ a]; its constructors are the declared ones together with [] and (:), Nothing and Just, Left and Right, and the constructors of each UU, at those sorts. A field of type aa is an XX field, a family or container application is a YY field of that sort, and any other type is a constant. Source values are finite or infinite constructor trees over Σ\Sigma: prefix-closed maps from finite paths to constructors that respect sorts and arities, with element and constant payloads at nonrecursive fields. This includes infinite Haskell lists, but does not model arbitrary Haskell computations. Let lower rename each sort and constructor of Σ\Sigma to its lowered counterpart at every node, and let π\pi rename lowered demand labels (Appendix § 25.§ 1) back to source constructors.

Theorem J.1 (Regular-container lowering). For every accepted regular declaration, lower is a bijection from source values over Σ\Sigma, finite or infinite, to lowered-family values at the corresponding root sort. It preserves occurrence paths, and hence both occurrence orders. The renaming extends to derivative records and finite trails. For the reference machine of § 6, runs from corresponding configurations correspond step by step, with demand labels related by π\pi. Finite lowering closure gives finite generated code.

Proof. Memoisation gives one lowered sort per sort of Σ\Sigma and one specialised constructor per source constructor, with the same fields in the same order and of the same kinds; Self becomes the sort of its own container application. The renaming is therefore a bijection of signatures that preserves arity, field order, field kind, and field sort. Applied at every node of a path map it yields a lowered value, and the inverse renaming undoes it; both act node by node, so infinite values need no limit argument. Paths keep their field positions, so occurrences and their orders are preserved. A derivative record retains the same tagged position and other fields under renaming; applying this correspondence to each frame preserves finite trails and their endpoint sorts. The reference machine inspects only the sort, tag, field order, and field kinds of each node, so its runs on tt and lower(tt) agree up to renaming, and π\pi maps each lowered demand label to its source constructor. A finite closure gives finitely many sorts and constructors, hence finite generated code. □

Proof sketches for cursor correctness

This appendix states the lemmas behind Theorem 6.1 and sketches their proofs. For finite values of single self-recursive datatypes, the artifact’s Lean development mechanisms Lemma K.1 in both directions; the theorems are sim_step, sim_step_rev, bsim_step, and, for matching the same source constructor, simulation_labels and bsimulation_labels in mechanisation/. The other lemmas, and simulation for families, are proved here on paper.

Proof of Theorem 6.1. Part 1 is Lemma K.1. Part 2 is Lemma K.2. Part 3 is Lemmas K.3, K.4, and K.5. □

Lemma K.1 (Simulation). Fix an accepted family description and a running configuration σ≈θ\sigma\approx\theta. If σ⟶σ′\sigma\longrightarrow\sigma', then θ\theta executes exactly one generated search clause, reaching θ′\theta' with σ′≈θ′\sigma' \approx\theta', and both steps demand the same source constructor, if any. Every clause executed from θ\theta arises in this way. Related configurations have equal root and current sorts and store the same fields, so encoded states are well typed.

Proof sketch of Lemma K.1. Fix σ≈θ\sigma\approx\theta and consider the form of σ\sigma.

Entry, σ=Enter⁡d(c(v),κ)\sigma= \operatorname{Enter}_{d}(c(v),\kappa). Then θ=seek⁡d(⌈κ⌉,c(v))\theta= \operatorname{seek}_{d}(\lceil\kappa\rceil,c(v)) matches cc, the only source match of the step, and emits (3) at ed(c)e_d(c). Its three cases are those of scan⁡d\operatorname{scan}_{d}. An XX field ℓ′\ell' gives Just⁡(Cursor⁡(⌈κ⌉,bc,ℓ′(v^ℓ′),vℓ′))\operatorname{Just}(\operatorname{Cursor}(\lceil\kappa\rceil,b_{c,\ell'}(\widehat{v}_{\ell'}),v_{\ell'})), which is related to Yield⁡(c,v,ℓ′,κ)\operatorname{Yield}(c,v,\ell',\kappa). A Yp′Y_{p'} field gives

seek⁡d(Snoc⁡(⌈κ⌉,kc,ℓ′(v^ℓ′)),vℓ′)=seek⁡d(⌈(c,ℓ′,v^ℓ′)::κ⌉,vℓ′),\operatorname{seek}_{d}(\operatorname{Snoc}(\lceil\kappa\rceil,k_{c,\ell'}(\widehat{v}_{\ell'})),v_{\ell'}) = \operatorname{seek}_{d}(\lceil(c,\ell',\widehat{v}_{\ell'}) :: \kappa\rceil,v_{\ell'}),

related to the reference successor and with current sort p′p' on both sides. No remaining field gives rise⁡d(⌈κ⌉,c(v))\operatorname{rise}_{d}(\lceil\kappa\rceil,c(v)).

Return, σ=Return⁡d(t,(c,ℓ,v^ℓ)::κ)\sigma= \operatorname{Return}_{d}(t,(c,\ell,\widehat{v}_{\ell}) :: \kappa). Then θ=rise⁡d(Snoc⁡(⌈κ⌉,kc,ℓ(v^ℓ)),t)\theta= \operatorname{rise}_{d}(\operatorname{Snoc}(\lceil\kappa\rceil,k_{c,\ell}(\widehat{v}_{\ell})),t). The frame tag identifies cc and ℓ\ell, the record supplies v^ℓ\widehat{v}_{\ell}, and tt supplies vℓv_{\ell}. The clause removes the frame, restoring the parent sort, and emits the scan after ℓ\ell on v^ℓ[ℓ:=t]\widehat{v}_{\ell}[\ell:= t], which is the reference successor; no source constructor is matched. On [ ][\,], rise⁡d\operatorname{rise}_{d} meets BNil⁡\operatorname{BNil} and returns Nothing⁡\operatorname{Nothing}, related to End.

Advance, σ=Advance⁡d(c,v,ℓ,κ)\sigma= \operatorname{Advance}_{d}(c,v,\ell,\kappa). Then θ\theta is the move from Cursor⁡(⌈κ⌉,bc,ℓ(v^ℓ),vℓ)\operatorname{Cursor}(\lceil\kappa\rceil,b_{c,\ell}(\widehat{v}_{\ell}),v_{\ell}). The body tag supplies cc and ℓ\ell and the focus supplies vℓv_{\ell}, so the move emits the same scan after ℓ\ell as the reference step. It matches only generated records, so neither step demands a source constructor.

The three running configurations call distinct generated functions, and each function selects a unique clause by its outer tag. Every executed clause therefore comes from the corresponding reference step, proving the converse. Each emitted record stores the fields of its indexed derivative summand, and pushing or popping a frame changes the current sort of the trail exactly as it changes that of the stack (Theorem 4.2), so related states have equal sorts and are well typed. □

Lemma K.2 (Mixed-operation preservation). Let a cursor be obtained by entry. After any finite sequence of successful next, previous, and replace operations, its trail and terminal record encode the stack and local position of a yield, and close reconstructs the represented root with all replacements in their selected positions.

Proof sketch of Lemma K.2. Entry produces the encoding of a yield by Lemma K.1. Simulation preserves the encoded stack and terminal record after each successful move, in either direction. Replacement changes only the selected element. Induction on the operation sequence therefore preserves the representation. Closing reconstructs its root by Theorem 4.2. □

Lemma K.3 (Navigation). On a finite, fully defined input, entry selects the first or last element occurrence, or reports that there are none. Each move selects the adjacent occurrence in its direction, and reports a boundary exactly when there is none.

Proof sketch of Lemma K.3. Induction on the remaining fields of a constructor shows that the reference scan visits its direct elements and recursive traversals in the specified order. A continuation returns to the field immediately after the completed child. Structural induction on a finite value then gives the full order and termination. Lemma K.1 gives the same result for generated code. □

Lemma K.4 (Reversibility). On a finite, fully defined input, a successful move followed by the opposite move restores an equal value and the marked position.

Proof sketch of Lemma K.4. The trail and terminal tag of a cursor determine the path of its occurrence: each frame kc,ℓk_{c,\ell} contributes the choice (c,ℓ)(c,\ell) and the terminal bc,ℓb_{c,\ell} the last one. A backward search from that configuration scans the fields before ℓ\ell at the current constructor and, on each return, the fields before the saved position at the next ancestor. By the definition of the orders it yields the greatest occurrence that precedes the current one in forward order, which is the occurrence a forward move has just left. The forward case is symmetric. Pointer identity may differ, because returning through a constructor may allocate it again. □

Lemma K.5 (Replacement). On a finite, fully defined input, replace changes only the selected occurrence.

Proof sketch of Lemma K.5. Replacement changes the selected field without inspecting it; each reconstruction clause inserts that field in the position named by its tag. □

References

  1. [1]Michael Abbott, Thorsten Altenkirch, Conor McBride, and Neil Ghani. 2005. ∂ for Data: Differentiating Data Structures. Fundamenta Informaticae 65, 1–2 (2005), 1–28.
  2. [2]Andreas Abel. 2010. MiniAgda: Integrating Sized and Dependent Types. In Proceedings Workshop on Partiality and Recursion in Interactive Theorem Provers (EPTCS, Vol. 43). Open Publishing Association, 14–28. doi:10.4204/EPTCS.43.2DOI
  3. [3]Michael D. Adams. 2010. Scrap Your Zippers: A Generic Zipper for Heterogeneous Types. In Proceedings of the 6th ACM SIGPLAN Workshop on Generic Programming (WGP). Association for Computing Machinery, New York, NY, USA, 13–24. doi:10.1145/1863495.1863499DOI
  4. [4]Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. 2007. Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson/Addison Wesley, Boston, MA, USA.
  5. [5]Thorsten Altenkirch, Neil Ghani, Peter Hancock, Conor McBride, and Peter Morris. 2015. Indexed Containers. Journal of Functional Programming 25 (2015), e5. doi:10.1017/S095679681500009XDOI
  6. [6]Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In Computer Science Logic (Lecture Notes in Computer Science, Vol. 4646). Springer, Berlin, Heidelberg, 208–222. doi:10.1007/978-3-540-74915-8_18DOI
  7. [7]Richard S. Bird. 2006. Loopless Functional Algorithms. In Mathematics of Program Construction (MPC 2006) (Lecture Notes in Computer Science, Vol. 4014). Springer, Berlin, Heidelberg, 90–114. doi:10.1007/11783596_9DOI
  8. [8]John H. Conway. 1971. Regular Algebra and Finite Machines. Chapman and Hall, London.
  9. [9]Olivier Danvy. 2008. Defunctionalized Interpreters for Programming Languages. In Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming (ICFP). Association for Computing Machinery, New York, NY, USA, 131–142. doi:10.1145/1411204.1411206
  10. [10]Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Ariya Ishihara, and Jan Willem Klop. 2010. Productivity of Stream Definitions. Theoretical Computer Science 411, 4–5 (2010), 765–782. doi:10.1016/j.tcs.2009.10.014
  11. [11]Bryan Ford. 2004. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). Association for Computing Machinery, New York, NY, USA, 111–122. doi:10.1145/964001.964011DOI
  12. [12]Peter Hancock, Dirk Pattinson, and Neil Ghani. 2009. Representations of Stream Processors Using Nested Fixed Points. Logical Methods in Computer Science 5, 3 (2009), 9:1–9:17. doi:10.2168/LMCS-5(3:9)2009DOI
  13. [13]Peter Hawkins, Alex Aiken, Kathleen Fisher, Martin Rinard, and Mooly Sagiv. 2011. Data Representation Synthesis. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). Association for Computing Machinery, New York, NY, USA, 38–49. doi:10.1145/1993498.1993504
  14. [14]Ralf Hinze and Johan Jeuring. 2003. Generic Haskell: Applications. In Generic Programming: Advanced Lectures. Roland Backhouse and Jeremy Gibbons (Eds.). Lecture Notes in Computer Science, Vol. 2793. Springer, Berlin, Heidelberg, 57–96. doi:10.1007/978-3-540-45191-4_2
  15. [15]Gérard Huet. 1997. The Zipper. Journal of Functional Programming 7, 5 (1997), 549–554. doi:10.1017/S0956796897002864
  16. [16]John Hughes, Lars Pareto, and Amr Sabry. 1996. Proving the Correctness of Reactive Systems Using Sized Types. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). Association for Computing Machinery, New York, NY, USA, 410–423. doi:10.1145/237721.240882DOI
  17. [17]Oleg Kiselyov. 2005. Generic Zipper: The Context of a Traversal. https://okmij.org/ftp/continuations/zipper.html Web article; code first posted to the Haskell mailing list on 27 April 2005, page last updated 11 April 2015.
  18. [18]Oleg Kiselyov and Chung-chieh Shan. 2007. Delimited Continuations in Operating Systems. In Modeling and Using Context: 6th International and Interdisciplinary Conference (Lecture Notes in Computer Science, Vol. 4635). Springer, Berlin, Heidelberg, 291–302. doi:10.1007/978-3-540-74255-5_22DOI
  19. [19]Edward A. Kmett. 2021. zippers: Traversal Based Zippers. https://hackage.haskell.org/package/zippers-0.3.2 Hackage package, version 0.3.2; accessed October 2026.
  20. [20]Tristan Knoth, Di Wang, Nadia Polikarpova, and Jan Hoffmann. 2019. Resource-Guided Program Synthesis. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). Association for Computing Machinery, New York, NY, USA, 253–268. doi:10.1145/3314221.3314602DOI
  21. [21]Calvin Loncaric, Emma Torlak, and Michael D. Ernst. 2016. Fast Synthesis of Fast Collections. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). Association for Computing Machinery, New York, NY, USA, 355–368. doi:10.1145/2908080.2908122DOI
  22. [22]Conor McBride. 2001. The Derivative of a Regular Type is its Type of One-Hole Contexts. Extended abstract, unpublished manuscript. http://strictlypositive.org/diff.pdf
  23. [23]Conor McBride. 2008. Clowns to the Left of Me, Jokers to the Right: Dissecting Data Structures. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL). Association for Computing Machinery, New York, NY, USA, 287–295. doi:10.1145/1328438.1328474DOI
  24. [24]Erik Meijer, Maarten M. Fokkinga, and Ross Paterson. 1991. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. In Functional Programming Languages and Computer Architecture, 5th ACM Conference (Lecture Notes in Computer Science, Vol. 523), John Hughes (Ed.). Springer, Berlin, Heidelberg, 124–144. doi:10.1007/3540543961_7DOI
  25. [25]John C. Reynolds. 1972. Definitional Interpreters for Higher-Order Programming Languages. In Proceedings of the ACM Annual Conference, Vol. 2. Association for Computing Machinery, New York, NY, USA, 717–740. doi:10.1145/800194.805852DOI
  26. [26]Luc Segoufin. 2013. Enumerating with Constant Delay the Answers to a Query. In Proceedings of the 16th International Conference on Database Theory (ICDT). Association for Computing Machinery, New York, NY, USA, 10–20. doi:10.1145/2448496.2448498DOI
  27. [27]Ben A. Sijtsma. 1989. On the Productivity of Recursive List Definitions. ACM Transactions on Programming Languages and Systems 11, 4 (1989), 633–649. doi:10.1145/69558.69563DOI
  28. [28]Alexey Rodriguez Yakushev, Stefan Holdermans, Andres Löh, and Johan Jeuring. 2009. Generic Programming with Fixed Points for Mutually Recursive Datatypes. In Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP). Association for Computing Machinery, New York, NY, USA, 233–244. doi:10.1145/1596550.1596585

Paper details

vlnc:W_a5cjthu4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Code, Codex

View statement
Looking for related papers…
Contents