Backtracking Iterators
📜 Abstract
Iterating over the elements of an abstract collection is usually done in ML using a fold-like higher-order function provided by the data structure. This article discusses a different paradigm of iteration based on purely functional, immutable cursors. Contrary to fold-like iterators, the iteration can be cleanly interrupted at any step. Contrary to imperative cursors (such as those found in C++ and Java libraries) it is possible to backtrack the iterator to a previous step. Several ways to iterate over binary trees are examined and close links with Gérard Huet’s Zipper are established. Incidentally, we show the well-known two-lists implementation of functional queues arising from a Zipper-based breadth-first traversal.
✨ Summary
Summary
The paper presents persistent, step-by-step iterators as an alternative to higher-order ML iterators and mutable object-oriented cursors. A persistent iterator returns both the next element and a new iterator state, leaving the previous state unchanged. This supports early termination without exceptions or auxiliary materialization and, more importantly, permits returning to earlier states during backtracking algorithms. The paper illustrates the approach with inorder, preorder, postorder, and breadth-first traversals of binary trees.
For depth-first traversals, the iterator state is represented by persistent stacks or compact traversal-specific structures. Breadth-first traversal is implemented with persistent queues represented by two lists, retaining amortized constant-time queue operations. The paper also shows that these iterator states can be derived systematically from Huet’s Zipper: a zipper records a focused subtree together with its path and surrounding context, and traversal operations can be expressed through zipper navigation. Continuation-passing-style implementations are discussed as another formulation; the paper observes that they are generally less efficient because closures produce larger iterator states and do not generalize as directly to breadth-first traversal.
The reported benchmarks show broadly comparable performance between the direct persistent implementations and zipper-derived implementations, while continuation-passing-style versions are consistently slower and use more memory, although still within a constant-factor relationship. The work identifies persistent iterators as useful abstractions for search, enumeration, graph traversal, and other algorithms requiring controlled traversal and backtracking. It also connects persistent iterators, zippers, persistent queues, and continuation-based control, providing a systematic functional-programming perspective rather than presenting a wholly new primitive. (lri.fr)
Influence and subsequent use
The paper’s ideas have been used and discussed in later functional-programming material. A 2016 tutorial explicitly follows the paper’s zipper treatment and translates its OCaml examples into Haskell. (carlo-hamalainen.net) The paper is also cited in later work on formally verified custom data generators, where iterator-like cursors are adapted for exhaustive generation and verified implementations in Why3. (scispace.com) A separate OCaml programming article cites the paper as background for a backtracking solution. (whoek.com) The available evidence indicates influence primarily on functional-programming techniques, cursor-based enumeration, and verified data-generation methods; no specific commercial-industry adoption was identified in the searched sources.