The Essence of the ITERATOR Pattern

The ITERATOR pattern gives a clean interface for element-by-element access to a collection. Imperative iterations using the pattern have two simultaneous aspects: mapping and accumulating . Various existing functional iterations model one or other of these, but not both simultaneously. We argue that McBride and Paterson’s idioms , and in particular the corresponding traverse operator, do exactly this, and therefore capture the essence of the ITERATOR pattern. We present some axioms for traversal, and illustrate with a simple example, the repmin problem.