"The Essence of the Iterator Pattern"(EIP) is the paper I liked the most last year. It gave me a brand new look over something which I had be using for years: the for
loop.
In this post I'll try to present some ideas of that paper and show how to implement the solution described by the authors using Scalaz-like code. A minimum previous exposure to functional programming, functors and monads will definitely help!
What's in a for loop?
That was really what hooked me. What do you mean "what's in a for
loop"?. Is there anything magic in that construct I've been using for years?
The introduction of EIP shows an example of a for
loop to iterate on elements (not the C-like for
used with an index). I'm transmogrifying it here to Scala but the idea remains the same:
val basket: Basket[Fruit] = Basket(orange, apple)
var count = 0
val juices = Basket[Juice]()
for (fruit <- basket) {
count = count + 1
juices.add(fruit.press)
}
We start from a "container" of fruits: Basket
. It could actually be anything, a List
, a Tree
, a Map
... Then the for
loop actually does 3 things:
- it returns a container having the same "shape";
juices
is still a Basket
- it accumulates some kind of measure. Here, the number of fruits in the
count
variable - it maps the elements to other elements: pressing the fruits to get some juice
And this for
loop is actually not the most complex:
- the
count
variable could influence the mapping of elements: juices.add(fruit.press(harder=count))
- we could have several variables depending on each other:
cumulative = cumulative + count
- the mapping could also influence a "measure" variable:
liquid = liquid + fruit.press.quantity
The purpose of EIP is to show that the "essence" of what happens in the for
loop above can be abstracted by an Applicative Traversal. And the authors go on showing that given this Applicative abstraction, we get an incredible modularity for programming.
The Applicative typeclass
How can an Applicative traversal be better than a for loop, and what does that even mean?? EIP has a lot of sentences and expressions which can be hard to grasp if you don't have a strong functional programming / Haskell background. Let's try to dissect that slowly and start with the formal definitions anyway.
What is a Functor?
The first thing we need to talk about is the Functor
typeclass:
trait Functor[F[_]] {
def fmap[A, B](f: A => B): F[A] => F[B]
}
One way of interpreting a Functor
is to describe it as a computation of values of type A
. For example List[A]
is a computation returning several values of type A
(non-deterministic computation), Option[A]
is for computations that you may or may not have, Future[A]
is a computation of a value of type A
that you will get later, and so on. Another way of picturing it is as some kind of "container" for values of type A
.
Saying that those computations are Functors
is essentially showing that we can have a very useful way of combining them with regular functions. We can apply a function to the value that is being computed. Given a value F[A]
and a function f
, we can apply that function to the value with fmap
. For example, fmap
is a simple map
for a List
or an Option
.
Pointed Functor
By the way, how do you even create a value of type F[A]
? One way to do that is to say that F[_]
is Pointed
:
trait Pointed[F[_]] {
def point[A](a: => A): F[A]
}
That is, there is a point
function taking a (call by name) value of type A
and returning a F[A]
. For example, a regular List
is Pointed
just by using the constructor for Lists:
object PointedList extends Pointed[List] {
def point[A](a: => A) = List(a)
}
Then combining the 2 capabilities, pointed and functor, gives you a PointedFunctor
:
trait PointedFunctor[F[_]] {
val functor: Functor[F]
val pointed: Pointed[F]
def point[A](a: => A): F[A] = pointed.point(a)
def fmap[A, B](f: A => B): F[A] => F[B] = functor.fmap(f)
}
The PointedFunctor
trait is merely the aggregation of a Pointed
and a Functor
.
What about Applicative
then? We're getting to it, the last missing piece is Applic
.
Applic
Applic
is another way to combine a "container" with a function.
Instead of using fmap
to apply the function to the computed value we suppose that the function is itself a computed value inside the container F
(F[A => B]
) and we provide a method applic
to apply that function to a value F[A]
:
trait Applic[F[_]] {
def applic[A, B](f: F[A => B]): F[A] => F[B]
}
Let's take an example. Say I have a way to compute the price of a Fruit
when the market is open:
def pricer(market: Market): Option[Fruit => Double]
If the market is closed, pricer
returns None
, because we don't know what are the prices. Otherwise it returns a pricing function. Now if I have a grow
function possibly returning a Fruit
:
def grow: Option[Fruit]
Then, using the Applic
instance, you can price the Fruit
:
val price: Option[Double] = applic(pricer(market)).apply(grow)
The price
will necessarily be an Option
because you may not have a pricer nor a Fruit
to price. And a bit of renaming and pimping reveals why we're using the term "Applicative":
val pricingFunction = pricer(market)
val fruit = grow
val price: Option[Double] = pricingFunction ⊛ fruit
In a way we're just doing a normal function application, but we're just doing it inside the Applicative container. Now we have all the pieces to build the Applicative
functor that EIP is talking about.
Applicative Functor
An Applicative Functor
is the aggregation of an Applic
and a PointedFunctor
:
trait Applicative[F[_]] {
val pointedFunctor: PointedFunctor[F]
val applic: Applic[F]
def functor: Functor[F] = new Functor[F] {
def fmap[A, B](f: A => B) = pointedFunctor fmap f
}
def pointed: Pointed[F] = new Pointed[F] {
def point[A](a: => A) = pointedFunctor point a
}
def fmap[A, B](f: A => B): F[A] => F[B] = functor.fmap(f)
def point[A](a: => A): F[A] = pointed.point(a)
def apply[A, B](f: F[A => B]): F[A] => F[B] = applic.applic(f)
}
Let's see how that can be implemented for a List
. fmap
and point
are straightforward:
def fmap[A, B](f: A => B): F[A] => F[B] = (l: List[A]) => l map f
def point[A](a: => A): F[A] = List(a)
apply
turns out to be more interesting because there are 2 ways to implement it, both of them being useful:
apply a list of functions to each element and gather the results in a List:
def apply[A, B](f: F[A => B]): F[A] => F[B] = (l: List[A]) =>
for { a <- l; func <- f } yield func(a)
zip
the list of functions to the list of elements to apply each function to each element
def apply[A, B](f: F[A => B]): F[A] => F[B] = (l: List[A]) =>
(l zip f) map (p => p._2 apply p._1)
There is even a third way to use List
as an Applicative
by using the fact that List
is a Monoid
. But more on that later, for now we still have to see how all of this relates to the for
loop...
Traversing the structure
When we do a for
loop, we take a "structure" containing some elements and we "traverse" it to return:
- that same structure containing other elements
- a value computed from the structure elements
- some combination of above
Gibbons & Oliveira argue that any kind of for loop can be represented as the following traverse
operation:
trait Traversable[T[_]] {
def traverse[F[_] : Applicative, A, B](f: A => F[B]): T[A] => F[T[B]]
}
That is, if the container/structure of type T
has this traverse
function using an Applicative F
, then we can do whatever we would do with a for
loop on it.
To get a better feel for this traverse
function, we're going to implement the Traversable
trait for a binary tree and then we'll see how can we loop
on that tree.
A Binary Tree
For all the other examples in this post, we're going to use a very simple binary tree:
sealed trait BinaryTree[A]
case class Leaf[A](a: A) extends BinaryTree[A]
case class Bin[A](left: BinaryTree[A], right: BinaryTree[A]) extends BinaryTree[A]
On the other hand, the first shot at the Traversable
implementation is barely readable!
def BinaryTreeIsTraversable[A]: Traversable[BinaryTree] = new Traversable[BinaryTree] {
def createLeaf[B] = (n: B) => (Leaf(n): (BinaryTree[B]))
def createBin[B] = (nl: BinaryTree[B]) =>
(nr: BinaryTree[B]) => (Bin(nl, nr): BinaryTree[B])
def traverse[F[_] : Applicative, A, B](f: A => F[B]):
BinaryTree[A] => F[BinaryTree[B]] = (t: BinaryTree[A]) => {
val applicative = implicitly[Applicative[F]]
t match {
case Leaf(a) => applicative.apply(applicative.point(createLeaf[B]))(f(a))
case Bin(l, r) =>
applicative.apply(applicative.apply(applicative.point(createBin[B]))(traverse[F, A, B](f).apply(l))).
apply(traverse[F, A, B](f).apply(r))
}
}
}
This is a shame because the corresponding Haskell code is so concise:
instance Traversable Tree where
traverse f (Leaf x) = pure Leaf ⊛ f x
traverse f (Bin t u) = pure Bin ⊛ traverse f t ⊛ traverse f u
A bit of pimping to the rescue and we can improve the situation:
def traverse[F[_] : Applicative, A, B](f: A => F[B]): BinaryTree[A] => F[BinaryTree[B]] = (t: BinaryTree[A]) => {
t match {
case Leaf(a) => createLeaf[B] ∘ f(a)
case Bin(l, r) => createBin[B] ∘ (l traverse f) <*> (r traverse f)
}
}
Informally the traverse
method applies the function f
to each node and "reconstructs" the tree by using the apply
method (<*>
) of the Applicative
functor.
That's certainly still some Ancient Chinese to you (as it was for me) so we'd better see the traverse
method at work now. But we need to take another detour :-)
Applicative Monoid
One simple thing we might want to do, when iterating on a BinaryTree
, is to get the content of that tree in a List
. To do that, we're going to use the 3rd way to use List
as an Applicative
, as mentioned earlier. It turns out indeed that any Monoid
(what is it?) gives rise to an Applicative
instance but in a way that's a bit surprising.
/** Const is a container for values of type M, with a "phantom" type A */
case class Const[M, +A](value: M)
implicit def ConstIsPointed[M : Monoid] = new Pointed[({type l[A]=Const[M, A]})#l] {
def point[A](a: => A) = Const[M, A](implicitly[Monoid[M]].z)
}
implicit def ConstIsFunctor[M : Monoid] = new Functor[({type l[A]=Const[M, A]})#l] {
def fmap[A, B](f: A => B) = (c: Const[M, A]) => Const[M, B](c.value)
}
implicit def ConstIsApplic[M : Monoid] = new Applic[({type l[A]=Const[M, A]})#l] {
def applic[A, B](f: Const[M, A => B]) = (c: Const[M, A]) => Const[M, B](implicitly[Monoid[M]].append(f.value, c.value))
}
implicit def ConstIsPointedFunctor[M : Monoid] = new PointedFunctor[({type l[A]=Const[M, A]})#l] {
val functor = Functor.ConstIsFunctor
val pointed = Pointed.ConstIsPointed
}
implicit def ConstIsApplicative[M : Monoid] = new Applicative[({type l[A]=Const[M, A]})#l] {
val pointedFunctor = PointedFunctor.ConstIsPointedFunctor
val applic = Applic.ConstIsApplic
}
In the code above, Const
is the Applicative
instance for a given Monoid
. Const
contains values of type T
where T
is a Monoid
and we progressively establish what are the properties that Const
must satisfy to be Applicative
.
it must first be Pointed
. Informally, the point
method puts the neutral element of the Monoid
in a Const
instance
then it must be a Functor
. Here the fmap
function doesn't do anything but changing the type of Const
from Const[M, A]
to Const[M, B]
finally it must be an Applic
where the apply
method of Applic
uses the append
method of the Monoid
to "add" 2 values and return the result in a Const
instance.
There is unfortunately a lot of typing vodoo thing here:
the type declaration for Const
is Const[A, +B]
. It has a type parameter B
which is actually not represented by a value in the Const
class! It is a phantom type. But it is actually indispensable to match the type declarations of the typeclasses
the type F
that is supposed to be Applicative
is... ({type l[A] = Const[T, A]})#l
. Ouch, this deserves some explanation!
What we want is not so hard. The type Const[A, B]
has 2 type parameters. We need a way to fix A
to be T
and get the resulting type which will have only one type parameter. The expression above is the most concise way to get this desired type:
{ type l = SomeType }
is an anonymous type with a type member called l
. We can access that type l
in Scala by using #
: { type l = SomeType }#l
Then, in { type l[A] = SomeType[T, A] }#l
, l
is a higher-kinded type, having a type variable A
(actually SomeType[T, A]
where T
is fixed)
That was a really long detour for a mere for
loop, isn't it? Now... profit!
Contents of a BinaryTree...
We're going to use the Traversable
instance for the BinaryTree
and the List Monoid Applicative
to get the contents of a BinaryTree
:
import Applicative._
val f = (i: Int) => List(i)
val tree = Bin(Leaf(1), Leaf(2))
(tree.traverse[...](f)).value must_== List(1, 2)
Simple, for each element of the tree, we put it in a List
then we let the List Monoid
do its magic and aggregate all the results as we traverse the tree. The only difficulty here is the limits of Scala type inference. The ...
stands for type annotations that the compiler requires:
tree.traverse[Int, ({type l[A]=Const[List[Int], A]})#l](f)
Not pretty :-(
Update: As pointed out by Ittay Dror in the comments,
List[Int]
is not an applicative by itself and we need to put this list into a
Const
value to make it usable by the
traverse
function.
This is actually done by an implicit conversion method,
liftConst
, provided by the
Applicative object
:
implicit def liftConst[A, B, M : Monoid](f: A => M): A => Const[M, B] =
(a: A) => Const[M, B](f(a))
Profit time
Not everything is lost! We can encapsulate a bit the complexity in this case. We can extract part of the code above and create a contents
method which will work on any of Traversable
instance (assume I'm pimping the following examples so that I can write tree.method
instead of method(tree)
):
val tree: BinaryTree[Int] = Bin(Leaf(1), Leaf(2))
tree.contents must_== List(1, 2)
This is based on the following definition:
def contents[A]: T[A] => List[A] = {
val f = (a: A) => Const[List[A], Any](List(a))
(ta: T[A]) => traverse[({type l[U]=Const[List[A], U]})#l, A, Any](f).apply(ta).value
}
It also turns out that the contents
function is a specialized version of something even more generic, the reduce
function, working with any Monoid
:
def contents[A]: T[A] => List[A] = reduce((a: A) => List(a))
def reduce[A, M : Monoid](reducer: A => M): T[A] => M = {
val f = (a: A) => Const[M, Any](reducer(a))
(ta: T[A]) => traverse[({type l[A]=Const[M, A]})#l, A, Any](f).apply(ta).value
}
The reduce
function can traverse any Traversable
structure with a function mapping each element to a Monoid
element. We've used it to get the contents of the tree but can as easily get the number of elements:
def count[A]: T[A] => Int = reduce((a: A) => 1)
tree.count must_== 2
Can it get simpler than this :-)? Actually in that case it can! Since we don't need (a: A)
at all we can use reduceConst
:
def reduceConst[A, M : Monoid](m: M): T[A] => M = reduce((a: A) => m)
def count[A]: T[A] => Int = reduceConst(1)
It's like a Scala standard reduce
on steroids because instead you don't need to provide a binary operation, you just need a Monoid
instance.
.... and shape of a BinaryTree
We've addressed the question of doing some kind of accumulation based on the elements in the tree, now we're going to "map" them.
Monads are Applicatives too!
The following map
method can be derived from the traverse
method (note that no type annotations are necessary in that case, yes!):
def map[A, B](mapper: A => B) = (ta: T[A]) => traverse((a: A) => Ident(mapper(a))).apply(ta).value
Here we're traversing with an Applicative
which is very simple, the Ident
class:
case class Ident[A](value: A)
The Ident
class is a simple wrapper around a value, nothing more. That simple class is an Applicative
. But how?
Easy. Ident
is actually a Monad
and we can construct an Applicative
instance from every Monad. This comes from the fact that a Monad
is both a PointedFunctor
and an Applic
:
trait Monad[F[_]] {
val pointed: Pointed[F]
val bind: Bind[F]
def functor: Functor[F] = new Functor[F] {
def fmap[A, B](f: A => B): F[A] => F[B] = (fa: F[A]) =>
bind.bind((a: A) => pointed.point(f(a))).apply(fa)
}
def pointedFunctor: PointedFunctor[F] = new PointedFunctor[F] {
val functor = Monad.this.functor
val pointed = Monad.this.pointed
}
def applic: Applic[F] = new Applic[F] {
def applic[A, B](f: F[A => B]) = a =>
bind.bind[A => B, B](ff => functor.fmap(ff)(a))(f)
}
def applicative: Applicative[F] = new Applicative[F] {
val pointedFunctor = Monad.this.pointedFunctor
val applic = Monad.this.applic
}
}
And the Ident
class is trivially a Monad
(having a pointed
and a bind
member):
implicit def IdentIsMonad = new Monad[Ident] {
val pointed = new Pointed[Ident] {
def point[A](a: => A): Ident[A] = Ident(a)
}
val bind = new Bind[Ident] {
def bind[A, B](f: A => Ident[B]): Ident[A] => Ident[B] =
(i: Ident[A]) => f(i.value)
}
}
We can use our brand new map
function now:
tree.map((i: Int) => i.toString) must_== Bin(Leaf("1"), Leaf("2"))
We can even use it to get the "shape" of our container and discard all the elements:
tree.shape must_== Bin(Leaf(()), Leaf(()))
The shape
method just maps each element to ()
.
Decompose / Compose
I recap. We implemented a very generic way to iterate over a structure, any kind of structure (as long as it's Traversable
), containing elements, any kind of element, with a function which does an "application", any kind of application. Among the possible "applications", we've seen 2 examples: collecting and mapping which are the essential operations that we usually do in a for
loop.
Specifically we were able to get the contents
of a tree and its shape
. Is there a way to compose those 2 operations into a decompose
operation that would get both the content and the shape at once? Our first attempt might be:
def decompose[A] = (t: T[A]) => (shape(t), contents(t))
tree.decompose must_== (Bin(Leaf(()), Leaf(())), List(1, 2))
This works but it is pretty naive because this requires 2 traversals of the tree. Is that possible to do just one?
Applicative products
This is indeed possible by noticing the following: the product of 2 Applicatives is still an Applicative.
Proof, proof. We define Product
as:
case class Product[F1[_], F2[_], A](first: F1[A], second: F2[A]) {
def tuple = (first, second)
}
I spare you the full definition of Product
as an Applicative
to just focus on the Applic
instance:
implicit def ProductIsApplic[F1[_] : Applic, F2[_] : Applic] =
new Applic[({type l[A]=Product[F1, F2, A]})#l] {
val f1 = implicitly[Applic[F1]]
val f2 = implicitly[Applic[F2]]
def applic[A, B](f: Product[F1, F2, A => B]) = (c: Product[F1, F2, A]) =>
Product[F1, F2, B](f1.applic(f.first).apply(c.first),
f2.applic(f.second).apply(c.second))
}
That's not too complicated, you just have to follow the types. What's more troubling is the amount of type annotations which are necessary to implement decompose
. Ideally we would like to write:
def decompose[A] = traverse((t: T[A]) => shape(t) ⊗ contents(t))
Where ⊗
is an operation taking 2 Applicative
s and returning their product. Again the lack of partial type application for Const
muddies the whole (upvote SI-2712 please!):
val shape = (a: A) => Ident(())
val content = (a: A) => Const[List[A], Unit](List(a))
val product = (a: A) => (shape(a).⊗[({type l[T] = Const[List[A], T]})#l](content(a)))
implicit val productApplicative =
ProductIsApplicative[Ident, ({type l1[U] = Const[List[A], U]})#l1]
(ta: T[A]) => { val (Ident(s), Const(c)) =
traverse[({type l[V] = Product[Ident, ({type l1[U] = Const[List[A], U]})#l1, V]})#l, A, Unit](product).
apply(ta).tuple
(s, c)
}
We can improve the code sligthly by moving the implicit definition for productApplicative
inside the Applicative
companion object:
object Applicative {
...
implicit def ProductWithListIsApplicative[A[_] : Applicative, B] =
ProductIsApplicative[A, ({type l1[U] = Const[List[B], U]})#l1]
}
Then no implicit val productApplicative
is necessary and the Applicative
imports will be all we need.
Collection and dispersal
There is another way to do things "in parallel" while traversing the structure. The collect
method that we're going to build will do 2 things:
- it will accumulate some kind of state, based on the elements that we meet
- it will map each element to another kind of element
So, as we're iterating, we can do a regular mapping while computing some kind of measure. But before that, we need to take a little detour (again?? Yes, again) with the State
monad.
The State
monad
The State
Monad is defined by:
trait State[S, +A] {
def apply(s: S): (S, A)
}
It is basically:
- an object keeping some previous "state", of type
S
- a method to extract a meaningful value from this "state", of type
A
- this method computes a new "state", of type
S
For example, a simple counter for the number of elements in a List[Int]
can be implemented by:
val count = state((n: Int) => (n+1, ()))
It takes the previous "count" number n
and returns the new state n+1
and the extracted value (()
here, because we don't need to extract anything special).
The State
type above is a Monad
. I encourage you to read "Learn You a Haskell" to get a better understanding on the subject. I will just show here that the flatMap
(or bind
) method of the Monad
typeclass is central in putting that State
to work:
val count = (s: String) => state((n: Int) => (n+1, s + n))
(count("a-") flatMap count flatMap count).apply(0) must_== (3, "a-012")
The count
function takes the latest computed string and returns a State
where we increment the current "state" by 1 and we have a new String as the result, where the current count is appended. So when we start with the string "a-"
and we flatMap
count
2 times, we get (3, "a-012")
where 3 is the number of times we've applied the n+1
function and "a-012"
the result of appending to the current string.
By the way, why do we need to apply(0)
?
When we do all the flatMap
s, we actually store "stateful computations". And they are executed only once we provide the initial state: 0
!
Collecting elements
Let's now define a collect
operation on Traversable
which will help us to count:
def collect[F[_] : Applicative, A, B](f: A => F[Unit], g: A => B) = {
val applicative = implicitly[Applicative[F]]
import applicative._
val application = (a: A) => point((u: Unit) => g(a)) <*> f(a)
traverse(application)
}
This collect
operation, defined in EIP, is different from the collect
operation on Scala collections which is the equivalent of filter + map
. The collect
of EIP is using 2 functions:
f: A => F[Unit]
which collects data from each element "effectfully" (that is, possibly keeping state)
g: A => B
which maps each element to something else
So we could say that the EIP collect
is a bit like fold + map
. Knowing this, we can use collect
to count elements and do some mapping:
val count = (i: Int) => state((n: Int) => (n+1, ()))
val map = (i: Int) => i.toString
tree.collect[({type l[A]=State[Int, A]})#l, String](count, map).apply(0) must_==
(2, Bin(Leaf("1"), Leaf("2")))
Here again the type annotations are obscuring the intent a bit and if type inference was perfect we would just read:
val count = (i: Int) => state((n: Int) => (n+1, ()))
val map = (i: Int) => i.toString
tree.collect(count, map).apply(0) must_== (2, Bin(Leaf("1"), Leaf("2")))
I don't know about you, but I find this a bit magical. With the Applicative
and Traversable
abstractions, we can assemble our program based on 2 independent functions possibly developed and tested elsewhere.
Dispersing elements
The next utility function proposed by EIP is the disperse
function. Its signature is:
def disperse[F[_] : Applicative, A, B, C](f: F[B], g: A => B => C): T[A] => F[T[C]]
What does it do?
f
is the Applicative
context that's going to evolve when we traverse the structure, but regardless of what the elements of type A
are g
is a function which, for each element of type A
says what to do with the current context value, B
, and map that element back to the structure
Please, please, a concrete example!
Say I want to mark each element of a BinaryTree
with its "number" in the Traversal (the "label"). Moreover I want to use the element name to be able to qualify this label:
// a BinaryTree of Doubles
val tree: BinaryTree[Double] = Bin(Leaf(1.1), Bin(Leaf(2.2), Leaf(3.3)))
// the "label" state returning integers in sequence
val labelling: State[Int, Int] = state((n: Int) => (n+1, n+1))
// for each element in the tree, and its label,
// produce a String with the name and label
val naming: Double => Int => String = (p1: Double) => (p2: Int) => p1+" node is "+p2
// testing by applying an initial state (label `0`) and
// taking the second element of the pair `(last label, resulting tree)`
tree.disperse[elided for sanity](labelling, naming).apply(0)._2 must_==
Bin(Leaf("1.1 node is 1"), Bin(Leaf("2.2 node is 2"), Leaf("3.3 node is 3")))
Note that the naming
function above is curried. A more familiar way to write it would be:
val naming: (Double, Int) => String = (p1: Double, p2: Int) => p1+" node is "+p2
But then you would have to curry that function to be able to use it with the disperse
function:
tree.disperse[...](labelling, naming.curried)
The implementation of disperse
is:
def disperse[F[_] : Applicative, A, B, C](f: F[B], g: A => B => C) = {
val applicative = implicitly[Applicative[F]]
import applicative._
val application = (a: A) => point(g(a)) <*> f
traverse(application)
}
It is using the very capabilities of the applicative functor, the point
method and the <*>
application.
An overview of traversals
We've seen in the 2 examples above that we get different, specialized, versions of the traverse
function by constraining how mapping and Applicative
effects occur. Here's a tentative table for classifying other specialized versions of the traverse
function:
function | map element | create state | mapped depend on state | state depend on element |
collect | X | X | | X |
disperse | X | X | X | |
measure | X | X | | |
traverse | X | X | X | X |
reduce | | X | | X |
reduceConst | | X | | |
map | X | | | |
The only function we haven't shown before is measure
. It is mapping and accumulating state but this accumulation does not depend on the current element. Here's an example:
val crosses = state((s: String) => (s+"x", ()))
val map = (i: Int) => i.toString
tree.measure(crosses, map).apply("") must_==
("xxx", Bin(Leaf("1"), Bin(Leaf("2"), Leaf("3"))))
Other than not looking very useful, the code above is also lying! It is not possible to have a measure
function accepting a State
monad without having to provide the usual ugly type annotations. So the actual example is:
tree.measureState(crosses, map).apply("") must_==
("xxx", Bin(Leaf("1"), Bin(Leaf("2"), Leaf("3"))))
where measureState
is a specialization of the measure
method to States
. I think that one take-away of this post is that it might be beneficial to specialize a few generic functions in Scala , like traverse
, collect
... for Const
and State
in order to avoid type annotations.
Composing traversals
There's another axis of composition that we haven't exploited yet.
In a for
loop, without thinking about it, you may write:
for (a <- as) {
val currentSize = a.size
total += currentSize
result.add(total)
}
In the body of that for
loop, you have statements with dependency on each other. In an Applicative
traversal, this translates to the Sequential composition of Applicatives. From 2 Applicatives
, we can create a third one which is their Sequential composition. More precisely, this means that if F1[_]
and F2[_]
are Applicatives
then F1[F2[_]]
is an Applicative
as well. You want the demonstration? Ok, go.
First, we introduce a utility function on ApplicFunctor
s:
def liftA2[A, B, C](function: A => B => C): F[A] => F[B] => F[C] =
fa => applic.applic(functor.fmap(function)(fa))
liftA2
allows to lift
a regular function of 2 arguments to a function working on the Applicative
arguments. This is using the fact that an ApplicFunctor
is a Functor
so we can apply function: A => B => C
to the "a
in the box", to get a F[B => C]
"in the box". And then, an ApplicFunctor
is an Applic
, so we can "apply" F[B]
to get a F[C]
Armed with this function, we can write the applic
method for F1[F2[_]]
:
implicit val f1ApplicFunctor = implicitly[ApplicFunctor[F1]]
implicit val f2ApplicFunctor = implicitly[ApplicFunctor[F2]]
val applic = new Applic[({type l[A]=F1[F2[A]]})#l] {
def applic[A, B](f: F1[F2[A => B]]) = (c: F1[F2[A]]) => {
f1ApplicFunctor.liftA2((ff: F2[A => B]) => f2ApplicFunctor.apply(ff))(f).apply(c)
}
}
It's not so easy to get an intuition for what the code above is doing except that saying that we're using previous definitions to allow a F1[F2[A => B]]
to be applied to F1[F2[A]]
.
In mere mortal terms, this means that if we do an Applicative
computation inside a loop and if we reuse that computation in another Applicative
computation, we still get an Applicative
computation. The EIP illustration of this principle is a crazy function, the assemble
function.
The assemble
function
The assemble
function takes the shape of a Traversable
and a list of elements. If there are enough elements it returns Some[Traversable]
filled with all the elements (+ the reminder), otherwise it returns None
(and an empty list). Let's see it in action:
// the "shape" to fill
val shape: BinaryTree[Unit] = Bin(Leaf(()), Leaf(()))
// we assemble the tree with an exact list of elements
shape.assemble(List(1, 2)) must_== (List(), Some(Bin(Leaf(1), Leaf(2))))
// we assemble the tree with more elements
shape.assemble(List(1, 2, 3)) must_== (List(3), Some(Bin(Leaf(1), Leaf(2))))
// we assemble the tree with not enough elements
shape.assemble(List(1)) must_== (List(), None)
What's the implementation of the assemble
function? The implementation uses 2 Monads
(which are also Applicatives
as we know now):
- the
State[List[Int], _] Monad
is going to keep track of what we've already consumed - the
Option[_] Monad
is going to provide, or not, an element to put in the structure - the composition of those 2 monads is
State[List[Int], Option[_]]
(our F1[F2[_]]
in the ApplicFunctor
definitions above
So we just need to traverse the BinaryTree
with one function:
def takeHead: State[List[B], Option[B]] = state { s: List[B] =>
s match {
case Nil => (Nil, None)
case x :: xs => (xs, Some(x))
}
}
The takeHead
function is a State
instance where each state application removes the first element of the list of elements if possible, and returns it in an Option.
This is why the result of the assemble
function, once we apply it to a list of elements, is of type (List[Int], Option[BinaryTree[Int]])
.
A recursive implementation
Just for the fun of comparison, I'm going to write a recursive version doing the same thing:
def assemble(es: List[Int], s: BinaryTree[Unit]) : (List[Int], Option[BinaryTree[Int]]) = {
(es, s) match {
case (Nil, _) => (es, None)
case (e :: rest, Leaf(())) => (rest, Some(Leaf(e)))
case (_, Bin(left, right)) => {
assemble(es, left) match {
case (l, None) => (l, None)
case (Nil, Some(l)) => (Nil, None)
case (rest, Some(l)) => assemble(rest, right) match {
case (r, None) => (r, None)
case (finalRest, Some(r)) => (finalRest, Some(Bin(l, r)))
}
}
}
}
}
assemble(List(1, 2, 3), shape) must_== (List(3), Some(Bin(Leaf(1), Leaf(2))))
It works, but it makes my head spin!
A classical for-loop implementation
By the way, what would be the real for
loop version of that functionality? That one is not so easy to come up with because AFAIK there's no easy way to iterate on a BinaryTree
to get a similar BinaryTree
with just a for
loop! So, for the sake of the argument, we're going to do something similar with just a List
structure:
def assemble[T](es: List[T], shape: List[Unit]) = {
var elements = es
var list: Option[List[T]] = None
for (u <- shape) {
if (!elements.isEmpty) {
list match {
case None => list = Some(List(elements.first))
case Some(l) => list = Some(l :+ elements.first)
}
elements = elements.drop(1)
} else {
list = None
}
}
(elements, list)
}
assemble(List(1, 2, 3), List((), ())) must_== (List(3), Some(List(1, 2)))
Contrast and compare with:
List((), ()).assemble(List(1, 2, 3)) must_== (List(3), Some(List(1, 2)))
where you just define List
as a Traversable
:
implicit def ListIsTraversable[A]: Traversable[List] = new Traversable[List] {
def traverse[F[_] : Applicative, A, B](f: A => F[B]): List[A] => F[List[B]] =
(l: List[A]) => {
val applicative = implicitly[Applicative[F]]
l match {
case Nil => applicative.point(List[B]())
case a :: rest =>
((_:B) :: (_: List[B])).curried ∘ f(a) <*> (rest traverse f)
}
}
}
The Applicative composition is indeed very powerful, but we're going to see that there are other ways to compose functions and use them with Traversables
.
Monadic composition
This paragraph is exploring the fine relationships between applicative composition and monadic composition when doing traversals. We've seen that Applicative
instances can be composed and that Monads
can be Applicative
. But Monads
can also be composed using the so-called Kleisli composition. If we have:
val f: B => M[C]
val g: A => M[B]
Then
val h: A => M[C] = f ∎ g // is also a function from a value to a Monad
If we have 2 "monadic" functions f
and g
, we can then compose them, in the Kleisli sense, and use the composed version for a traversal. Indeed we can, but does this traversal have "nice properties"? Specifically, do we have:
traverse(f ∎ g) == traverse(f) ∎ traverse(g)
The answer is... it depends.
Monad commutativity
EIP shows that, if the Monad
is commutative, then this will always be true. What is a commutative Monad
you ask?
A Monad
is commutative if for all mx: M[X]
and my: M[Y]
we have:
val xy = for {
x <- mx
y <- my
} yield (x, y)
val yx = for {
y <- my
x <- mx
} yield (x, y)
xy == yx
This is not the case with the State Monad
for example:
val mx = state((n: Int) => (n+1, n+1))
val my = state((n: Int) => (n+1, n+1))
xy.apply(0) must_== (2, (1, 2))
yx.apply(0) must_== (2, (2, 1))
Monadic functions commutativity
Another slightly different situation is when we have a non-commutative Monad
but commutative functions:
val plus1 = (a: A) => state((n: Int) => (n+1, a))
val plus2 = (a: A) => state((n: Int) => (n+2, a))
val times2 = (a: A) => state((n: Int) => (n*2, a))
Here plus1
and times2
are not commutative:
(0 + 1) * 2 != (0 * 2) + 1
However it is obvious that plus1
and plus2
are commutative. What does that mean when we do a traversal?
If we traverse a simple List of elements using monadic composition we get:
List(1, 2, 3).traverse(times2 ∎ plus1) === 22
List(1, 2, 3).traverse(times2) ∎ List(1, 2, 3).traverse(plus1) === 32
We get different results. However, when f
and g
commute we get the same result:
List(1, 2, 3).traverse(plus2 ∎ plus1) === 10
List(1, 2, 3).traverse(plus2) ∎ List(1, 2, 3).traverse(plus1) === 10
Applicative composition vs Monadic composition
Another question we can ask ourselves is: if we consider the monadic functions as applicative functions (because each Monad
is Applicative
), do we get the nice "distribution" property we're after? The answer is yes, even when the functions are not commutative:
List(1, 2, 3).traverse(times2 ⊡ plus1) === 4
List(1, 2, 3).traverse(times2) ⊡ List(1, 2, 3).traverse(plus1) === 4
Well... more or less. The real situation is a bit more complex. List(1, 2, 3).traverse(times2 ⊡ plus1)
returns a State[Int, State[Int, List[Int]]]
while the second expression returns a State[Int, List[State[Int, Int]]
so what I'm hiding here is some more manipulations to be able to query the final result with some kind of join
.
Conclusion
You wouldn't believe it but I've only shown here half of the ideas presented in EIP!
To finish off this post here's 3 take-away points that I've learned while writing it:
functional programming is also about mastering some of these higher-level control structures like Applicative
. Once you master them, your toolbox expands considerably in power (just consider the assemble
example)
Scalaz is an incredible library but somewhat obscure to the beginner. For this post I've rewritten all the typeclasses I needed to have, and lots of examples (using specs2 of course). That gave me a much better understanding of the Scalaz functionality. You may consider doing the same to learn Scalaz (my code is available on github)
Scala is lacking behind Haskell in terms of type inference and it's a real pain for higher-order, generic programming. This can be sometimes encapsulated away by specializing generic functions to very common types (like traverseState
instead of traverse
). Again, please upvote SI-2712!
Finally, I want to mention that there are many other Haskell functional pearls waiting to be transliterated to Scala. I mean, it's a shame that we don't have yet any equivalent for "Learn you a Haskell" or "Typeclassopedia" in the Scala world. I hope that my post, like this other one by Debasish Ghosh, will also contribute to bridge the gap.