Home

The Essence of the Iterator Pattern

Jeremy Gibbons and Bruno C. d. S. Oliveira (2006). The Essence of the Iterator Pattern. Submitted for publication.

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.

The core of the solution is from McBride and Paterson's paper Applicative programming with effects, which wasn't posted to the home page before, but which was mentioned a couple of times in the LtU forum.

The context of this reseach is previous attempts to capture functional analogues of OOP design patterns:

Recently we have argued that pure datatype-generic maps are the functional analogue of the Iterator design pattern. It was partly while reflecting on that argument that we came to the (contradictory) position presented here.

By Ehud Lamm at 2006-04-13 11:26 | Functional | other blogs | 13917 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Idioms?

So, I read through this paper as best I could, and after the 2nd read I still couldn't fully follow it, but I was wondering: isn't what he's calling an idiom a pre-monad? Is there some sort of isomorphism between pre-monads and "applicative functors" (which I confess to not understanding)?

Thanks!

By jimdesu at Mon, 2006-04-17 16:38 | login or register to post comments

Applicative Functors

O'Caml's module system provides applicative functors out of the box; you can find the technical details in entry number 32 on Xavier Leroy's publications page. Also, Oleg Kiselyov's Applicative translucent functors in Haskell is recommended for both the O'Caml and Haskell communities, as O'Caml is used as a point of departure, and the article is literate code containing both languages.

By Paul Snively at Mon, 2006-04-17 19:38 | login or register to post comments

Uh...

I'm pretty sure McBride is using the term in a totally different sense than the O'Caml(/ML) community. He's using it as as a form of categorical functor that can be applied.

Compare the following for the difference between a premonad and a applicative functor:

class PreMonad m where
    fmap :: (a → b) → (m a → m b)
    unit :: a → m a

class ApplicativeFunctor m where
    ap :: m (a → b) → (m a → m b)
    pure :: a → m a

Note that ap takes an m (a → b) not just an (a → b).

By Derek Elkins at Tue, 2006-04-18 19:23 | login or register to post comments

Confession

I have to gleefully confess that my Category-Theory-fu is insufficient to be able to identify whether the senses here are different or not. If they are different, it strikes me as unfortunate, since the module community (O'Caml/ML or otherwise) already has a pretty good idea as to what's meant by "applicative functor," and there's extant literature on it.

By Paul Snively at Tue, 2006-04-18 19:39 | login or register to post comments

Race

Whichever is first on Wikipedia wins.

By Sjoerd Visscher at Wed, 2006-04-19 09:11 | login or register to post comments