Chapter 5 of Datatype-Generic Programming, the last one before Conclusions, is called “The Essence of the Iterator pattern,” the same name of the paper Gibbons and Oliveira wrote in 2006. The one available online as The Essence of the Iterator Pattern is from 2009. Reading this paper as a continuation of DGP gives it a better context.

Here’s the example given at the beginning of this paper, translated to Java.

```
public static <E> int loop(Collection<E> coll) {
int n = 0;
for (E elem: coll) {
n = n + 1;
doSomething(elem);
}
return n;
}
```

EIP:

We emphasize that we want to capture both aspects of the method

loopand iterations like it:mappingover the elements, and simultaneouslyaccumulatingsome measure of those elements.

The first half of the paper reviews functional iterations and applicative style. For applicative functors, it brings up the fact that there are three kinds of applicatives:

- Monadic applicative functors
- Naperian applicative functors
- Monoidal applicative functors

We’ve brought up the fact that all monads are applicatives many times. Naperian applicative functor zips together data structure that are fixed in shape.

Appliactive functors were originally named *idom* by McBride and Paterson,
so Gibbons uses the term *idiomatic* interchangably with *applicative* througout this paper,
even though McBride and Paterson renamed it to applicative functors.

A second family of applicative functors, this time non-monadic, arises from constant functors with monoidal targets.

We can derive an applicative functor from any `Monoid`

,
by using `empty`

for `pure`

, and `|+|`

for `ap`

.
The `Const`

datatype is also called `Const`

in Cats:

```
/**
* [[Const]] is a phantom type, it does not contain a value of its second type parameter `B`
* [[Const]] can be seen as a type level version of `Function.const[A, B]: A => B => A`
*/
final case class Const[A, B](getConst: A) {
/**
* changes the type of the second type parameter
*/
def retag[C]: Const[A, C] =
this.asInstanceOf[Const[A, C]]
....
}
```

In the above, the type parameter `A`

represents the value,
but `B`

is a phantom type used to make `Functor`

happy.

```
scala> import cats._, cats.data._, cats.implicits._
import cats._
import cats.data._
import cats.implicits._
scala> Const(1) map { (_: String) + "!" }
res0: cats.data.Const[Int,String] = Const(1)
```

When `A`

forms a `Semigroup`

, an `Apply`

is derived,
and when `A`

form a `Monoid`

, an `Applicative`

is derived automatically.

Computations within this applicative functor accumulate some measure: for the monoid of integers with addition, they count or sum…

```
scala> Const(2).retag[String => String] ap Const(1).retag[String]
res1: cats.data.Const[Int,String] = Const(3)
```

herding cats — Const datatype