Skip to main content

The Essence of the Iterator Pattern

Jeremy Gibbons and Bruno César dos Santos Oliveira

Abstract

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 applicative functors, 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 wordcount problem.

Journal
Journal of Functional Programming
Note
Revised version of Gibbons&Oliveira2006:Essence
Number
3&4
Pages
377−402
Volume
19
Year
2009