In 2006 the same author wrote The Essence of the Iterator Pattern. Linked is the revised 2009 version. This paper discusses applicative style by breaking down the GoF Iterator pattern into two aspects: mapping and accumulating.
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: 1. Monadic applicative functors 2. Naperian applicative functors 3. 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. Also apparently appliactive functors were originally named idiom, so idiomatic in this paper means applicative.
Scalaz implements Monoid[m].applicative to turn any monoids into an applicative.
scala> Monoid[Int].applicative.ap2(1, 1)(0)
res99: Int = 2
scala> Monoid[List[Int]].applicative.ap2(List(1), List(1))(Nil)
res100: List[Int] = List(1, 1)
EIP:
Like monads, applicative functors are closed under products; so two independent idiomatic effects can generally be fused into one, their product.
In Scalaz, product is implemented under Applicative typeclass:
trait Applicative[F[_]] extends Apply[F] with Pointed[F] { self =>
...
/**The product of Applicatives `F` and `G`, `[x](F[x], G[x]])`, is an Applicative */
def product[G[_]](implicit G0: Applicative[G]): Applicative[({type λ[α] = (F[α], G[α])})#λ] = new ProductApplicative[F, G] {
implicit def F = self
implicit def G = G0
}
...
}
Let’s make a product of List and Option.
scala> Applicative[List].product[Option]
res0: scalaz.Applicative[[α](List[α], Option[α])] = scalaz.Applicative$$anon$2@211b3c6a
scala> Applicative[List].product[Option].point(1)
res1: (List[Int], Option[Int]) = (List(1),Some(1))
The product seems to be implemented as a Tuple2. Let’s use Applicative style to append them:
scala> ((List(1), 1.some) |@| (List(1), 1.some)) {_ |+| _}
res2: (List[Int], Option[Int]) = (List(1, 1),Some(2))
scala> ((List(1), 1.success[String]) |@| (List(1), "boom".failure[Int])) {_ |+| _}
res6: (List[Int], scalaz.Validation[String,Int]) = (List(1, 1),Failure(boom))
EIP:
Unlike monads in general, applicative functors are also closed under composition; so two sequentially-dependent idiomatic effects can generally be fused into one, their composition.
This is called compose under Applicative:
trait Applicative[F[_]] extends Apply[F] with Pointed[F] { self =>
...
/**The composition of Applicatives `F` and `G`, `[x]F[G[x]]`, is an Applicative */
def compose[G[_]](implicit G0: Applicative[G]): Applicative[({type λ[α] = F[G[α]]})#λ] = new CompositionApplicative[F, G] {
implicit def F = self
implicit def G = G0
}
...
}
Let’s compose List and Option.
scala> Applicative[List].compose[Option]
res7: scalaz.Applicative[[α]List[Option[α]]] = scalaz.Applicative$$anon$1@461800f1
scala> Applicative[List].compose[Option].point(1)
res8: List[Option[Int]] = List(Some(1))
EIP:
The two operators
⊗and⊙allow us to combine idiomatic computations in two different ways; we call them parallel and sequential composition, respectively.
The fact that we can compose applicatives and it remain applicative is neat. I am guessing that this characteristics enables modularity later in this paper.
EIP:
Traversal involves iterating over the elements of a data structure, in the style of a
map, but interpreting certain function applications idiomatically.
The corresponding typeclass in Scalaz 7 is called Traverse:
trait Traverse[F[_]] extends Functor[F] with Foldable[F] { self =>
def traverseImpl[G[_]:Applicative,A,B](fa: F[A])(f: A => G[B]): G[F[B]]
}
This introduces traverse operator:
trait TraverseOps[F[_],A] extends Ops[F[A]] {
final def traverse[G[_], B](f: A => G[B])(implicit G: Applicative[G]): G[F[B]] =
G.traverse(self)(f)
...
}
Here’s how we can use it for List:
scala> List(1, 2, 3) traverse { x => (x > 0) option (x + 1) }
res14: Option[List[Int]] = Some(List(2, 3, 4))
scala> List(1, 2, 0) traverse { x => (x > 0) option (x + 1) }
res15: Option[List[Int]] = None
The option operator is injected to Boolean, which expands (x > 0) option (x + 1) to if (x > 0) Some(x + 1) else None.
EIP:
In the case of a monadic applicative functor, traversal specialises to monadic map, and has the same uses.
It does have have similar feel to flatMap, except now the passed in function returns G[B] where [G: Applicative] instead of requiring List.
EIP:
For a monoidal applicative functor, traversal accumulates values. The function reduce performs that accumulation, given an argument that assigns a value to each element.
scala> Monoid[Int].applicative.traverse(List(1, 2, 3)) {_ + 1}
res73: Int = 9
I wasn’t able to write this as traverse operator.
EIP:
In addition to being parametrically polymorphic in the collection elements, the generic traverse operation is parametrised along two further dimensions: the datatype being traversed, and the applicative functor in which the traversal is interpreted. Specialising the latter to lists as a monoid yields a generic contents operation.
scala> def contents[F[_]: Traverse, A](f: F[A]): List[A] =
Monoid[List[A]].applicative.traverse(f) {List(_)}
contents: [F[_], A](f: F[A])(implicit evidence$1: scalaz.Traverse[F])List[A]
scala> contents(List(1, 2, 3))
res87: List[Int] = List(1, 2, 3)
scala> contents(NonEmptyList(1, 2, 3))
res88: List[Int] = List(1, 2, 3)
scala> val tree: Tree[Char] = 'P'.node('O'.leaf, 'L'.leaf)
tree: scalaz.Tree[Char] = <tree>
scala> contents(tree)
res90: List[Char] = List(P, O, L)
Now we can take any data structure that supports Traverse and turn it into a List. We can also write contents as follows:
scala> def contents[F[_]: Traverse, A](f: F[A]): List[A] =
f.traverse[({type l[X]=List[A]})#l, A] {List(_)}
contents: [F[_], A](f: F[A])(implicit evidence$1: scalaz.Traverse[F])List[A]
The other half of the decomposition is obtained simply by a map, which is to say, a traversal interpreted in the identity idiom.
The “identity idiom” is the Id monad in Scalaz.
scala> def shape[F[_]: Traverse, A](f: F[A]): F[Unit] =
f traverse {_ => ((): Id[Unit])}
shape: [F[_], A](f: F[A])(implicit evidence$1: scalaz.Traverse[F])F[Unit]
scala> shape(List(1, 2, 3))
res95: List[Unit] = List((), (), ())
scala> shape(tree).drawTree
res98: String =
"()
|
()+-
|
()`-
"
EIP:
This pair of traversals nicely illustrates the two aspects of iterations that we are focussing on, namely mapping and accumulation.
Let’s also implement decompose function:
scala> def decompose[F[_]: Traverse, A](f: F[A]) = (shape(f), contents(f))
decompose: [F[_], A](f: F[A])(implicit evidence$1: scalaz.Traverse[F])(F[Unit], List[A])
scala> decompose(tree)
res110: (scalaz.Tree[Unit], List[Char]) = (<tree>,List(P, O, L))
This works, but it’s looping the tree structure twice. Remember a product of two applicatives are also an applicative?
scala> def decompose[F[_]: Traverse, A](f: F[A]) =
Applicative[Id].product[({type l[X]=List[A]})#l].traverse(f) { x => (((): Id[Unit]), List(x)) }
decompose: [F[_], A](f: F[A])(implicit evidence$1: scalaz.Traverse[F])(scalaz.Scalaz.Id[F[Unit]], List[A])
scala> decompose(List(1, 2, 3, 4))
res135: (scalaz.Scalaz.Id[List[Unit]], List[Int]) = (List((), (), (), ()),List(1, 2, 3, 4))
scala> decompose(tree)
res136: (scalaz.Scalaz.Id[scalaz.Tree[Unit]], List[Char]) = (<tree>,List(P, O, L))
Since the above implementation relys on type annotation to get the monoidal applicative functor, I can’t write it as nice as the Haskell example:
decompose = traverse (shapeBody ⊗ contentsBody)
There’s a useful method that Traverse introduces called sequence. The names comes from Haskell’s sequence function, so let’s Hoogle it:
`haskell sequence :: Monad m => [m a] -> m [a]` Evaluate each action in the sequence from left to right, and collect the results.
Here’s sequence method:
/** Traverse with the identity function */
final def sequence[G[_], B](implicit ev: A === G[B], G: Applicative[G]): G[F[B]] = {
val fgb: F[G[B]] = ev.subst[F](self)
F.sequence(fgb)
}
Instead of Monad, the requirement is relaxed to Applicative. Here’s how we can use it:
scala> List(1.some, 2.some).sequence
res156: Option[List[Int]] = Some(List(1, 2))
scala> List(1.some, 2.some, none).sequence
res157: Option[List[Int]] = None
This looks cool. And because it’s a Traverse method, it’ll work for other data structures as well:
scala> val validationTree: Tree[Validation[String, Int]] = 1.success[String].node(
2.success[String].leaf, 3.success[String].leaf)
validationTree: scalaz.Tree[scalaz.Validation[String,Int]] = <tree>
scala> validationTree.sequence[({type l[X]=Validation[String, X]})#l, Int]
res162: scalaz.Validation[String,scalaz.Unapply[scalaz.Traverse,scalaz.Tree[scalaz.Validation[String,Int]]]{type M[X] = scalaz.Tree[X]; type A = scalaz.Validation[String,Int]}#M[Int]] = Success(<tree>)
scala> val failedTree: Tree[Validation[String, Int]] = 1.success[String].node(
2.success[String].leaf, "boom".failure[Int].leaf)
failedTree: scalaz.Tree[scalaz.Validation[String,Int]] = <tree>
scala> failedTree.sequence[({type l[X]=Validation[String, X]})#l, Int]
res163: scalaz.Validation[String,scalaz.Unapply[scalaz.Traverse,scalaz.Tree[scalaz.Validation[String,Int]]]{type M[X] = scalaz.Tree[X]; type A = scalaz.Validation[String,Int]}#M[Int]] = Failure(boom)
EIP:
We have found it convenient to consider special cases of effectful traversals, in which the mapping aspect is independent of the accumulation, and vice versa. The first of these traversals accumulates elements effectfully, with an operation of type
a → m (), but modifies those elements purely and independently of this accumulation, with a function of typea → b.
This is mimicking the use of for loop with mutable variable accumulating the value outside of the loop. Traverse adds traverseS, which is a specialized version of traverse for State monad. Using that we can write collect as following:
scala> def collect[F[_]: Traverse, A, S, B](t: F[A])(f: A => B)(g: S => S) =
t.traverseS[S, B] { a => State { (s: S) => (g(s), f(a)) } }
collect: [F[_], A, S, B](t: F[A])(f: A => B)(g: S => S)(implicit evidence$1: scalaz.Traverse[F])scalaz.State[S,scalaz.Unapply[scalaz.Traverse,F[A]]{type M[X] = F[X]; type A = A}#M[B]]
scala> val loop = collect(List(1, 2, 3, 4)) {(_: Int) * 2} {(_: Int) + 1}
loop: scalaz.State[Int,scalaz.Unapply[scalaz.Traverse,List[Int]]{type M[X] = List[X]; type A = Int}#M[Int]] = scalaz.package$State$$anon$1@3926008a
scala> loop(0)
res165: (Int, scalaz.Unapply[scalaz.Traverse,List[Int]]{type M[X] = List[X]; type A = Int}#M[Int]) = (4,List(2, 4, 6, 8))
EIP:
The second kind of traversal modifies elements purely but dependent on the state, with a binary function of type
a → b → c, evolving this state independently of the elements, via a computation of typem b.
This is the same as traverseS. Here’s how we can implement label:
scala> def label[F[_]: Traverse, A](f: F[A]): F[Int] =
(f.traverseS {_ => for {
n <- get[Int]
x <- put(n + 1)
} yield n}) eval 0
label: [F[_], A](f: F[A])(implicit evidence$1: scalaz.Traverse[F])F[Int]
It’s ignoring the content of the data structure, and replacing it with a number starting with 0. Very effecty. Here’s how it looks with List and Tree:
scala> label(List(10, 2, 8))
res176: List[Int] = List(0, 1, 2)
scala> label(tree).drawTree
res177: String =
"0
|
1+-
|
2`-
"
EIP seems to be a popular paper to cover among Scala fp people.
Eric Torreborre (@etorreborre)’s The Essence of the Iterator Pattern is the most thorough study of the paper. It also covers lots of ground works, so it’s worth digging in.
Debasish Ghosh (@debasishg)’s Iteration in Scala - effectful yet functional is shorter but covering the good part by focusing on Scalaz.
Marc-Daniel Ortega (@patterngazer)’s Where we traverse, accumulate and collect in Scala also covers sequence and collect using Scalaz.
We’ll pick it up from here later.