ML 2006 START Conference Manager    

Backtracking Iterators

Jean-Christophe Filliatre

The 2006 ACM SIGPLAN Workshop on ML (ML 2006)
Portland, Oregon, 16th September 2006


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 Gerard 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.

START Conference Manager (V2.52.7)