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.

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 saved frames reaches its next element or the boundary within work and constructor-demand bounds affine in , provided each demanded constructor is produced in finite time (Theorem 8.2).
For the rose tree, the bounds are transitions and constructor demands; 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; at G in Figure 1. With Silent, the analysis emits no move certificate, and no bound depending only on 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 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 for labels, for trees, and 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
which keeps the fields in order: the label, the earlier siblings, the hole where the path continues, and the later siblings. The terminal context has type , a hole for the focused label followed by its children, and the focus adds an . Differentiation (written ; § 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 mutually recursive datatypes, called sorts. Each sort is a finite sum of finite ordered products:
Here is the set of constructors of sort and is the number of fields of constructor . The element parameter is ; names recursive child sorts, and ranges over field types independent of and all . A summand’s degree in 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 the products and 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 , 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 and the field grammar
Each 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.

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 for the least fixed point, allowing only finite unfoldings of the bound recursion, and for the greatest fixed point, which also admits infinite unfoldings. The rules below are for one sort, with constructor set ; § 4.1 supplies their family indices and § 8 their reading at .
We write for the standard derivative [1, 22]. Its rules on a constructor body are:
Here is the empty type and the unit type. The rules for swap the roles of and . Differentiating in each variable gives
A stores the context around one recursive child; a 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:
The square marks the hole; it is not a stored field. The compiler emits one record constructor per summand, tagged by . Its fields are exactly the fields of other than , in source order: the fields, then the fields. The record’s generated name encodes the tag, so it identifies the constructor and where the hole falls between the and fields.
Representing traversal histories
Kamot stores the path of frames with the most recently crossed frame at its accessible end (§ 2). Write and for forward and backward lists of , 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: is FCons 1 (FCons 2 (FCons 3 FNil))) and exposes , while is Snoc (Snoc (Snoc BNil 1) 2) 3 and exposes .
An element context either stops at a terminal context in or passes through a frame of to the context of a child. Its finite-path presentation is the path equation [1], where abbreviates the sum over the summands of . Each step contains one , whatever the degree of in : 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 keeps the fields left of its hole and right of it. Rebuilding the value wraps each step around the rest of the path, so the surrounding fields, read left to right, are , then the terminal , then . 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 , write for its left fields, first step to last, and for its right fields, last step to first.
Lemma 4.1 (Path–trail correspondence). For , , and independent of , there is a bijection
It is order-preserving: if a path corresponds to , then , , lists the context’s stored fields in their original left-to-right order. Converting a path of steps, in either direction, takes structural work (§ 7) and allocates spine cells.
Proof. See Appendix § 24. □
Applied to the path equation, the lemma gives the element contexts and the zippers that focus an element:
For a list, data List a = Nil | Cons a (List a), a step has type , and the terminal context stores the rest of the list. So
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 and . A path from a tree to its first child crosses Tree List0 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
Here names a parent sort and one of its recursive child sorts. Differentiating with respect to , the type of an immediate child of sort , gives : the information needed to reconstruct an after returning from a . Differentiating with respect to gives , the terminal context for a selected element field of sort :
Each summand of again splits at its hole as , for and , and its record’s name now also gives the sort . For the rose tree, and are : a node has no tree field, and a List0 cell has no label. Finite paths form the least solution of this equation:
For the rose tree it reads
A path from a root is thus a finite, well-sorted sequence of frames ending at some current sort , followed by a . Theorem 4.2 represents it by a backward trail from to , nearest frame exposed:
Theorem 4.2 (Indexed path–trail correspondence). For every root sort , there is a bijection, order-preserving in the sense of Lemma 4.1,
Here is the type of finite, well-sorted frame paths from to . Extending such a path by one frame and removing its nearest frame take constant structural work. Adding the selected field to its terminal context yields exactly one marked element occurrence in a value of root sort .
Proof. Use an accumulator whose current-sort index is part of its type. It starts empty at . On a summand with , append the -to- frame, which keeps both sides and its tag, and continue with current sort ; on , return the accumulator and that terminal. Frame order is unchanged. Conversely, start with , remove each exposed final frame, and wrap the residual context between its and 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 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
Kamot stores each such crumb as several indexed frames (§ 2).
Generating zipper operations
For every one-sort datatype, Kamot emits the zipper type 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 and recursive field of , and Body one for each element field. Each is with field removed: it keeps the fields before 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 and fields active. Given a current position in a constructor and a direction (forward or backward), the compiler finds the next active field after in direction ; at constructor entry, is forward and 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 be the variables bound by the constructor pattern and let omit ; is the trail. Write and for the constructors Frame_c_ℓ′ and Body_c_ℓ′. The entry function finds the first element of a subtree in direction ; the resumption function continues in the parent once a child is finished. The three outcomes are emitted as
Constant fields () are retained but never examined by this search.
The rule also produces the bodies of the public moves. A clause matches a source constructor, saving a frame at each step down; a clause matches the nearest frame and binds the completed child to the missing variable .
The public next and previous match the cursor’s terminal record, bind the focused element to , and continue after that position; openFirst and openLast are 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 target syntax nodes. The ordinary family backend also specialises reconstruction helpers to each of the root sorts; its total output is therefore bounded by 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 is a finite list of records : returning a child fills the omitted field and resumes after . Stacks are sorted like trails: if is a constructor of sort and , pushing turns into a stack in . The empty stack marks the root, and in each configuration below the value or constructor belongs to the current sort of .
There are three running configurations:
There are also suspended configurations and a terminal configuration . Define by selecting the next active field strictly after in direction :
Computing inspects one constructor description at the meta level and costs no transition. The running configurations step as follows:
Here and are the entry positions, and inserts at position . Requesting another element resumes a yield as an Advance configuration; changing direction changes 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 , and a yielded local position becomes . Formally, stacks encode as trails, and , so for .
The relation relates and to and , respectively. A yield relates to . An of that yield relates to a move in direction from its cursor, and relates to . 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 is trail depth, is the length of the operation’s reference search, and count constructor and element occurrences in the root.
| operation | control steps | source demand |
| focus, replace | none | |
| close | none | |
| openFirst/openLast | ordered reference search | |
| next/previous | ordered reference search | |
| traverse | complete 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 ; for certified directions, § 8 bounds and the constructor demands, with uniform move bound (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 , and a root value , and let be the reference run from to its first Yield or End. Then openFirst () or openLast () on executes one generated search clause per step of , with the same source demand, on every finite prefix of . If ends after steps, the operation takes 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 , and a valid cursor , and let be the reference run from of the yield that encodes to the next Yield or End. Then next () or previous () from satisfies the conclusions of Theorem 7.1 for .
Theorem 7.3 (Local-operation contract). At a valid cursor of depth , focus, replace, and close take , , and 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).
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 bound all source constructor arities. For a fixed description , tag dispatch and constructor arities are bounded, so each search clause has bounded structural cost independent of input size and depth. We write when the hidden constant may depend on .
Theorem 7.4 (Structural work). A search of reference steps executes exactly generated search clauses and incurs structural work and allocation. A complete traversal in one direction of a finite input, including the final boundary result, executes exactly generated search clauses:
where counts source constructor occurrences across the family’s unfolding and counts element occurrences. Its structural work is . At a cursor of depth , focus and replace have constant structural overhead, and close takes 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 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 entry and return clauses. Each element yields once and is advanced past once, contributing move clauses. No other search clause is executed. This proves Equation (4), in either direction. Since , the structural bound follows for fixed .
Reading or replacing the focus accesses a fixed cursor field. Closing reconstructs the terminal constructor and then removes one frame for each of the 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 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 . 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 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 , a reachable cursor still has a finite history. Its finite-path contexts have the form
where and are the recursive and element derivatives evaluated at . 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 and prefix edges in direction are the least relations closed under
Here means that field precedes in direction . Prefix edges pass earlier nullable children because those children may return empty.
A summary records separate yield and return outcomes, each with a pair bounding transitions and demanded constructors. Impossible outcomes are omitted. The entry summary covers a search that enters a value of sort , 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 summarise a field suffix , excluding its initial control action. An empty suffix returns with , an element yields with , and constants are skipped. For a recursive field ,
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 charge pays for the child’s return. Entry adds 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 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 and be the componentwise maxima over the possible outcomes of terminal and of frame continuations, using for an empty collection. The move certificate at depth is
The final 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 , with productive demanded roots. A bounded root-entry summary guarantees a yield or boundary within 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 . 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 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
| yield | return | |
| Tree | impossible | |
| List0 |
Table 11.
Both terminal and frame continuation maxima are , giving transitions and demands per move, where 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 and trail frames , nearest first, let and 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 , of for , and of , omitting terms with an impossible outcome.
Proof. As in the proof of Theorem 8.2, Lemma G.2 bounds the terminal segment by and the th frame segment by . All earlier segments return; only the last can yield. □
Let , , , be the componentwise maxima of the yield and return outcomes of terminal and frame continuations, taking when no continuation has that outcome. For , Theorem 8.3 gives the uniform bound
For the rose tree, and , so the demand bound falls from to and the transition bound stays . For a label in a value of sort Tree, let count its ancestors and the earlier siblings along its path, so . Theorem 8.3 gives transitions and demands (Appendix § 22). Only the demand bound depends solely on source depth. At G, , , and . § 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 .
For each root sort , is bounded if and only if one constant bounds the transitions of root entry on all finite values of sort .
A move certificate is emitted if and only if some function of alone bounds the transitions of every move from a valid cursor at depth on finite values.
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 or bounded by no function of . 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 executes at most transitions and returns a result or suspended state. For , a scheduler runs next directly when ; otherwise, or without a certificate, it runs runFor .
Corollary 8.5 (Contract-directed slicing). For a move from a valid cursor on productive demanded roots, each scheduler invocation with budget executes at most 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 and a demand budget . It admits a move when a certificate is present and
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 from pending source subtrees . For the rose tree, the container-level frame is
Completed siblings lie to the left of the hole and pending siblings to its right; setting 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 shared by all sorts. The algebra for sort has type . 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 constructors therefore takes exactly 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 and 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 and are attained and never exceeded. The values are shallow (), so these checks test the bounds, not their slopes.
| Datatype | Dir. | Emitted | Separated | Moves | Ratio |
| List | fwd | ; 1 | ; 1 | 90 | 1.00 |
| List | bwd | ; 0 | 2; 0 | 90 | 1.00 |
| Event log | fwd | ; 1 | ; 1 | 112 | 1.00 |
| Event log | bwd | ; 0 | 2; 0 | 112 | 1.00 |
| Rose tree | fwd | ; | ; | 352 | 1.00 |
| File system | fwd | ; | ; | 246 | 1.00 |
| Data.Map shape | fwd | ; | ; | 178 | 1.00 |
| Located module | fwd | ; | ; | 715 | 0.88 |
| Annotated lambda | fwd | ; | ; 1 | 1,077 | 0.67 |
| Postfix lambda | bwd | ; | ; 1 | 875 | 0.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 . 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.
| Implementation | Code | Bound | ns/request | bytes/request | live KiB |
| Kamot cursor | declaration | yes | 107 | 200 | 426 |
| Handwritten explicit stack cursor | no | 113 | 263 | 394 | |
| McBride generic dissection | encoding | no | 560 | 1,058 | 1,273 |
| External zippers | traversal | no | 690 | 4,237 | 3,126 |
| Direct recursive rescan | search | no | 4,940 | 19,045 | 394 |
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 entry-guarded in direction when every constructor containing a recursive field has an element field before its first recursive field in direction . Equivalently, its first active field is . 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 is entry-guarded in direction and let bound its number of recursive fields per constructor. On productive demanded roots, entry in direction yields or terminates in at most two search clauses. A move in direction from a valid cursor at depth yields or terminates within search clauses, where
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 existing ancestors. At most previously unvisited recursive fields per such constructor cost at most two clauses each, and completing each of these 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 , let be the direct elements of 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 , complete cursor enumeration and the eager fold with the ordered-elements algebra both return .
Proof. The cursor result follows from the traversal specification: every direct element is yielded once, in constructor-field order. For the fold, induction on 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 and (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 and : the cursor is selected when , 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 and , 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 and Theorem C.1 establishes for a completed eager fold. Comparing the two is equivalent to comparing with . 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 direct element fields, , and 4,096 links, so and . Every policy builds and consumes the same ordered element list. Comparing with selects the faster of the cursor and the unbounded eager fold at all five tested densities: the cursor is 2.9 times faster at , and the fold 2.1 times faster at . At 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.
| Selected plan | Cursor | Fold | Fold, fuel 31 | Recursive | |
| 0 | Cursor | 20.2 | 40.2 | 54.9 | 5.3 |
| 1 | Cursor | 52.5 | 152.6 | 150.0 | 89.7 |
| 2 | Fold | 252.4 | 120.5 | 236.0 | 180.6 |
| 4 | Fold | 331.8 | 180.7 | 222.9 | 191.2 |
| 8 | Fold | 620.8 | 307.0 | 324.3 | 223.3 |
Table 3. Common-output batch traversal: median s 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 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 have distinct element seeds. Roots with may share, and serve only as an empty-output control.
The unbounded fold is faster than the fuel-31 fold at every density except , where the medians differ by 2% and the ranges overlap. Control counts alone do not determine elapsed time: the fold’s count is at every density, while its time ranges from 40.2 to 307.0 s. Direct recursion is faster than both generated plans at and but provides neither generated cursor navigation nor the fold’s suspension interface.
The batch timings depend on GHC inlining: at GHC inlines next into the enumeration loop, which allocates 104 bytes per element, while at 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 determines the catamorphism : recursively fold each child to a , then apply to that layer. For a family, the backend emits one indexed machine interface per root sort and an algebra family . Kamot uses a common result type across sorts. Each algebra processes one completed constructor layer.
Refining the recursive derivative
For left-to-right evaluation, a frame for recursive field retains earlier recursive fields at type , later ones at type , and nonrecursive fields at their original types:
Here replaces the recursive variable by . Setting 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 , the two recursive positions give : 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 , representing the suspended ancestors by with the nearest frame exposed. Replacing a frame after completing a child takes constant structural work for fixed .
For a family, a frame from parent sort to child sort retains earlier family children as results and later children as source values:
Here 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 return resumes only a frame awaiting its result, at the statically known parent sort.
One extension would give each sort its own result type , with algebras . An earlier child of sort would then contribute a , while a pending child would retain its source type . For the lowered rose tree, Tree could produce and List0 could produce , making the container-level algebra directly expressible. The current backend uses a common 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 fields in declaration order, forcing each child result to weak head normal form. Finally it applies 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 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 transitions: descents, applications, and returns. Its structural
overhead is , 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 . A transition inspects and constructs only bounded-size records for fixed . 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 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 , the compiler compile applied to 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 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 s, within 4% of the handwritten stack’s 209 s, but allocates 671 KiB rather than 512 KiB. Running it in 31-transition budgets costs 238 s and 894 KiB. The generated machine provides suspension at higher allocation than either baseline.
| Policy | s/tree | KiB/tree |
| Kamot eager fold | 216 | 671 |
| Kamot fold, fuel 31 | 238 | 894 |
| Handwritten explicit stack | 209 | 512 |
| Direct recursive fold | 173 | 160 |
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 . 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 , 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 s per submitted query and certified admission takes 8.38–9.11 s. 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 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.
| Work | Demand | Policy | Answers | Wasted | s | bytes |
| 64 | 8 | Fuelled | 128 | 1,024 | 9.54 | 18,151 |
| 64 | 8 | Certified | 128 | 0 | 8.77 | 16,841 |
| 256 | 32 | Fuelled | 143 | 3,616 | 12.08 | 22,018 |
| 256 | 32 | Certified | 128 | 0 | 8.55 | 16,007 |
| 512 | 256 | Fuelled | 256 | 0 | 16.52 | 30,077 |
| 512 | 256 | Certified | 243 | 0 | 14.48 | 27,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 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 is at most 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.
| Input | Policy | ns/label | bytes/label | Max steps | Max slice |
| Balanced | Direct | 66.8 | 895 | 46 | 4 |
| Fuelled | 68.5 | 919 | 46 | 2 | |
| Contract-directed | 66.8 | 895 | 46 | 3 | |
| Deep return | Direct | 123.8 | 895 | 32,774 | 356 |
| Fuelled | 130.8 | 920 | 128 | 5 | |
| Contract-directed | 127.5 | 920 | 128 | 3 | |
| Sparse | Direct | 17,030 | 178,189 | 1,542 | 20 |
| Fuelled | 17,663 | 178,497 | 128 | 4 | |
| Contract-directed | 18,657 | 178,497 | 128 | 6 |
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 . Maximum step counts are deterministic.
On the deep-return input, the seven per-process maxima range from 325 to 857 for direct search and from 3 to 19 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 , 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 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 (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).
| Input | Total | Largest search | ||
| Log, 1,000 events | 1,001 | 1,000 | 3,002 | 1,003 |
| Balanced syntax, height 9 | 1,023 | 1,023 | 3,069 | 11 |
| Skewed syntax, 512 applications | 1,025 | 1,025 | 3,075 | 4 |
| Sparse tree, empty height 10 | 2,051 | 2 | 4,104 | 4,098 |
Table 7. Measured abstract clause counts for complete forward traversals. Every row satisfies . 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.
| Policy | ns/request | bytes/request | live KiB |
| Kamot cursor | 25 | 247 | 202 |
| External zippers | 152 | 1,216 | 919 |
| Direct recursive rescan | 2,839 | 1,332 | 170 |
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 . A move from depth consequently uses at most 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 point | ns/request | Range | bytes/request |
| Navigation and edits | 270 | 252–329 | 482 |
| Polynomial result | 613 | 591–628 | 850 |
| Native tree | 604 | 555–669 | 1,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 transitions and 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.
| Policy | Mixed ns | Mixed bytes | Deep let chain ns | Deep let chain bytes |
| KAMOT family cursor | 78 | 246 | 58 | 253 |
| Handwritten indexed stack | 78 | 246 | 56 | 253 |
| Handwritten unindexed stack | 87 | 357 | 38 | 309 |
| Rescan | 3,757 | 16,384 | 3,396 | 11,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 (); constructor count alone fits less well (). 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 of sort and later returns from without an intervening yield, then .
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 field and every field of an entered node is itself entered and returned from. The entered nodes form a finite tree rooted at . Induction on its height, applying the nullability rule at each node, shows that every entered sort, in particular , is nullable. Constant fields are never entered, so they may hold any value. □
Lemma G.2 (Suffix summary soundness). Let be any ordered suffix of a constructor’s fields with a bounded summary , and assume demanded roots are productive. Suppose every entry summary consulted in computing 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 , with any well-sorted field values and stack, reaches a yield or the surrounding constructor’s pending return within the corresponding bound of . The bound excludes the control action that starts the scan. No condition is imposed on the fields preceding .
Proof. Induct on the length of . The empty suffix returns and an element field yields, each with cost ; skipping a constant changes neither cost nor outcome. For , soundness of gives two possibilities. A child yield ends the scan within . A child return costs at most before its pending return action; that action costs and resumes at , with induction hypothesis applies. These are exactly the alternatives in the rules for . 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 was consulted in computing , 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 for the order in which bounded entry summaries are evaluated, so depends only on summaries with and . A sort without constructors has no values, and both of its outcomes are impossible.
Claim A. Let be bounded, a finite or infinite value of sort , and any well-sorted stack. The run from reaches either a Yield within or the configuration within , counting transitions and constructor demands, and only an outcome that marks possible occurs.
We prove Claim A by induction on . Let . The entry step matches and costs . For the scan of ’s fields we prove Claim B: for each suffix of the fields of in direction that the scan can reach without yielding, it reaches a Yield within or the end of within .
We induct on the length of . The empty, element, and constant cases are as in the proof of Lemma G.2. Suppose . The scan reached this field without yielding, so every earlier active field of is a field whose child returned empty, and by Lemma G.1 each of those sorts is nullable. The edge rule therefore gives , so and Claim A holds for the child of sort .
The child segment either yields within , which ends the scan, or reaches its pending return within . In the latter case the return step costs , demands nothing, and resumes the scan at , where the induction hypothesis applies. This is the rule of § 8.1 for . 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 . The child 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 encodes a yield whose stack holds records. A move from a cursor whose terminal context records constructor and position performs one advance step and scans the fields after . 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 . If this segment reaches the pending return from , returning through the nearest frame starts its suffix; including that return action gives . 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 such frame segments run, and the final root return to End costs one further step with no demand. Summing gives and . 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 ancestors contributes one Frame_Tree_Node_1 and one Frame_List0_List0Cons_0. Each earlier sibling contributes one Frame_List0_List0Cons_1, so for such siblings. Their return outcomes are , , and , respectively; the terminal return outcome is . If every segment returns, the move costs at most , including the final root return. A yielding segment replaces its return outcome by and skips the remaining frames and root return. Thus every move is bounded by : 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 is fixed. By Lemma K.1 it suffices to count reference steps.
Lemma H.1 (Element-free values). For every nullable sort there is a finite value of sort that contains no element, and a run entering returns from it after finitely many steps without yielding.
Proof. Induct on the derivation of . Its last rule names a constructor with no 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 , then for every value of sort there is a value of sort , finite apart from , whose entry reaches after at least one step and without yielding.
Proof. The edge rule names a constructor of sort and a field with such that every active field before in direction is a field of nullable sort. Let with , 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 , skips constants, enters and returns from each earlier child without yielding, and then enters . □
Lemma H.3 (Pumping). If is unknown, then for every there is a finite value of sort such that a run entering takes at least steps without yielding, and there is a productive infinite value of sort , 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 consisting of a finite stem followed by a repeated cycle. Applying Lemma H.2 along its first edges, with any finite value at the end, gives ; each edge costs at least one step and no yield. Construct 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 . □
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 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 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 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 is unknown for a root sort , root entry on the value of Lemma H.3 takes at least steps.
Part 2. Suppose no move certificate is emitted. Some terminal or frame suffix , following field of a constructor of sort , then has an unknown summary. Thus contains a recursive field with unknown , preceded only by constants and nullable recursive fields. Because the family is inhabited, sort occurs at some node of a finite value of a root sort. Replace the subtree at that node by , where is an element if is a terminal suffix and a finite value containing an element if is a frame suffix; the fields of before hold element-free values, the field holds , and the remaining fields hold finite values. Fix the surrounding context and all finite fillers independently of . In the terminal case, place the cursor at . In the frame case, place it at the last element of in direction ; its move returns from after finitely many steps and then runs the frame suffix .
Lemma H.4 ensures that entry and finitely many moves reach this cursor. No ancestor of its focus lies inside , so its trail depth is fixed. Its next move crosses the element-free fields and enters , taking at least steps. Each pumped edge enters a new constructor, so demands are unbounded too. Thus no function of bounds these moves, proving the reverse implication of part 2.
Part 3. Replace by . The prefix reaching the cursor visits only its finite ancestors and the fields preceding the focus in direction ; 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 for the paths, with constructors and , where , , , and . A history is a value of , built from BNil and Snoc. Paths are finite because is a least fixed point, and histories are finite by definition. The left-to-right order of a path’s fields is
For steps , outermost first, and terminal , this is . From the definitions of § 4,
and both are empty for BNil.
The map and its inverse. Define by , where
Define by , where
One recursive call of is a transfer: it moves the outermost step of the residual path, with both its fields, onto the history. One recursive call of is the inverse transfer. The function recurses on a smaller path and on a smaller history, so both terminate.
Invariant. A state pairs a history with a residual path. Its reading is the sequence , , . The states and both read as
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 . The run of starts in state , whose reading is , and ends in state , whose reading is , , . By the invariant the two readings are equal, which is the order-preservation property.
Mutual inverses. First, for all and , by induction on . For , both sides equal . For ,
by the definitions of and and the induction hypothesis. Taking gives .
Second, for all and , by induction on . For , both sides equal . For ,
Taking gives . Hence is a bijection with inverse .
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 , , and . 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 steps, performs transfers and one final Stop match, which allocates the result pair. On a history of steps, allocates one Stop cell, performs inverse transfers, and ends with one BNil match. Each direction thus takes structural work and allocates spine cells.
No stored value is inspected. Every clause of and matches only a path constructor, a history constructor, or a pair. The definitions are parametric in , , and : each stored , , or 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.
Contract semantics and lowering
Ordinary cursor contracts
A contract for operation is a record : 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
where is a natural constant and . Ordinary cursor counts are exact; fuelled drivers instead report the upper bound for a transition budget . The fold backend reports 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
For cursor operations, means no source demand, records constructor matches up to the next yield or boundary in direction , and 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; records the assumptions stated in § 7.
Label every reference and generated control step by either , when it exposes source constructor , or , otherwise. Write
for a finite prefix of generated control steps of from state , with source-label trace , and write when such a prefix ends in public result . 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 and state , let be the reference run from the corresponding configuration: for entry at root , and of the decoded yield for a move. It stops at its first Yield or End and may be infinite. For traverse, is the complete reference traversal to End; focus, replace, and close run no search, and their is empty.
For a contract of , a natural-valued valuation agrees with when each of , , occurring in or is assigned its corresponding finite depth or count. If occurs and is finite, is its length; an infinite run imposes no condition on . Unused variables impose no condition. Thus a local move requires no finite size for the surrounding input, whereas the complete-traversal contract requires finite and .
Write for the value of under , using ordinary arithmetic and maximum. The descriptor is the label trace of ; denotes the trace of the complete reference traversal and the empty trace. The judgement holds when every source state agreeing with and satisfying has all three properties below. An operation satisfies a contract when the judgement holds for every .
Partial correctness. If , then is finite, , , and, for entry and moves, encodes the final configuration of . Focus returns the selected element, replacement changes only that occurrence, and closing rebuilds the root.
Prefix correspondence. For entry, moves, and complete traversal, the generated run and 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.
Conditional termination. If is present and demanded roots are productive, is finite and its length and demand count satisfy the bounds of .
For an uncertified move, and 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 , 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 count. For Theorem 7.3, focus and replacement take zero control steps and inspect no source constructor. Closing takes 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 , Maybe , Either , or 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 . Its sorts are the declared types and the container applications in the finite closure, such as ; its constructors are the declared ones together with [] and (:), Nothing and Just, Left and Right, and the constructors of each , at those sorts. A field of type is an field, a family or container application is a field of that sort, and any other type is a constant. Source values are finite or infinite constructor trees over : 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 to its lowered counterpart at every node, and let 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 , 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 . Finite lowering closure gives finite generated code.
Proof. Memoisation gives one lowered sort per sort of 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 and lower() agree up to renaming, and 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 . If , then executes exactly one generated search clause, reaching with , and both steps demand the same source constructor, if any. Every clause executed from 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 and consider the form of .
Entry, . Then matches , the only source match of the step, and emits (3) at . Its three cases are those of . An field gives , which is related to . A field gives
related to the reference successor and with current sort on both sides. No remaining field gives .
Return, . Then . The frame tag identifies and , the record supplies , and supplies . The clause removes the frame, restoring the parent sort, and emits the scan after on , which is the reference successor; no source constructor is matched. On , meets and returns , related to End.
Advance, . Then is the move from . The body tag supplies and and the focus supplies , so the move emits the same scan after 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 contributes the choice and the terminal the last one. A backward search from that configuration scans the fields before 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]Michael Abbott, Thorsten Altenkirch, Conor McBride, and Neil Ghani. 2005. ∂ for Data: Differentiating Data Structures. Fundamenta Informaticae 65, 1–2 (2005), 1–28.
- [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]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]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]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]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]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]John H. Conway. 1971. Regular Algebra and Finite Machines. Chapman and Hall, London.
- [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]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]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]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]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]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]Gérard Huet. 1997. The Zipper. Journal of Functional Programming 7, 5 (1997), 549–554. doi:10.1017/S0956796897002864
- [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]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]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]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]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]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]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]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]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]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]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]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]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