← All papers
First page of Datatypes In, Zippers Out!

Datatypes In, Zippers Out!

Smayan Agarwal, Aalok Thakkar

cs.PL Nov 17, 2026 · v1
A Lean 4 development mechanises simulation, move and trail bounds, and completeness of generated zipper code for finite single self-recursive datatypes.
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.

Datatype derivatives give one-hole context types, but they do not fix a zipper's concrete representation or specify its navigation costs and the constructors it forces. Programmers need zipper implementations whose correctness and operational behaviour are guaranteed, including on productive, potentially infinite inputs.

Kamot compiles regular algebraic datatypes in a restricted Haskell fragment, including mutual recursion and nested containers, into zipper modules that keep backward trails of frames. A reference machine relates the generated clauses to an ordered traversal. A compositional analysis over nullability and prefix edges derives move bounds that are affine in trail depth, and constructor-demand bounds, for certified directions. The one-sort finite results are mechanised in Lean 4 using only core Lean; families, container lowering, and infinite-input bounds are proved on paper.

Lean 4 verifies lockstep simulation, termination, root-entry and move bounds, trail-sum 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 type-checks, and independent checkers validate certificates, traces, and bounds. A prefetching workload shows that budgeted searches avoid discarded source evaluations, but conservative bounds can lose some answers that fuelled search finds.