Skip to main content

The Essence of the Iterator Pattern

Jeremy Gibbons and Bruno César dos Santos Oliveira


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

Book Title
Mathematically−Structured Functional Programming
Conor McBride and Tarmo Uustalu
Superseded by Gibbons&Oliveira2008:Essence