Last Updated: February 25, 2016

Generalizing the Reader Tooling, part 1

This post is part of a series where I incrementally build up the Reader dependency injection tool, using different advanced concepts of functional programming in scala:

Generalizing Common Functions

In the previous post on tooling the Reader Monad, I presented some code to help deal with common operations with the Reader Monad. Please read the previous posts as I will skip the long introduction in this post and go for quite complex scala.

Just a short intro on Reader, it's a wrapper, a bit like Option or Future, that defines a dependency on a resource (e.g. a data source), before returning a result. For instande readUser(id: Long): Reader[UserConnection, User] is a function that will read a user from a DB, given a UserConnection and return a User. As UserConnection is not a concrete connection, it's up to the caller of the function to eventually provide an implentation. The good thing with Reader is that it provides the map and flatMap methods, so you can compose it with other readers before having to provide a concrete implementation.

Here are two of the functions that I had proposed to simplify the use of Readers:


def sequence[C, R](list: Traversable[Reader[C, R]]): Reader[C,Traversable[R]] = reader { conn =>
   for { r <- list } yield r(conn)
}

implicit def moveFuture[A, B](future: Future[Reader[A, B]])(implicit context: ExecutionContext): Reader[A, Future[B]] = (conn: A) => {
  for (r <- future) yield r(conn)
}

sequence takes a traversable (a collection) of Readers, and moves the collection into the Reader: Traversable[Reader[_, R]] => Reader[_, Traversable[R]].
moveFuture takes a future of a reader and moves the future inside the reader: Future[Reader[_, R]] => Reader[_, Future[R]]

If you look at the code and the semantic of the functions, they basically do the same thing. The actual code is exactly the same; this is because both Future and Traversable have a map function to transform the values that they are wrapping.

What if we could abstract that and have only one function to move things that have a map function around the Reader? That would be good, but Traversable and Future do not have a common ancestor that provides map. This is where typeclasses are used, so let's see how it works.

The CanMap Typeclass

There is a good explanation of what typeclasses are at marakana, I recommend that you watch it before reading further if you do not know what's a Typeclass.

A typeclass in scala allows you to add features to classes that you can't modify. Imagine the problem described previously: we want to tell the compiler that Future and Traversable follow the same interface as they provide map and flatMap. However, we can't go an change the scala libraries to add a common interface to these two types, and there are many other potential types that also provide such functions that we can't always modify (Option for instance).

Let's first define a trait with what we want:


trait CanMap[A, B, M[_]] {
  def map(l: M[A])(f: A => B): M[B]
  def flatMap(l: M[A])(f: A => M[B]): M[B]
}

CanMap describes the behaviour of a type M that contains some value (Option, Future, Seq, …) and on which we can apply the method map and flatMap. This is basically what a typeclass is, it defines general behaviour of a set of types.

Let's see how we can define this behaviour for the Option class:


class OptCan[A, B] extends CanMap[A, B, Option] {
   def map(l: Option[A])(f: A => B): Option[B] = l.map(f)
   def flatMap(l: Option[A])(f: A => Option[B]): Option[B] = l.flatMap(f)
}

That's a pretty simple implementation as it only proxies the map and flatMap functions to the real implementations of Option. There are more complex typeclasses that would create whole new methods (like exporting to Json) for a whole set of types.

But, how do we use this typeclass? Let's rewrite the sequence method to use it:


def sequence[C, R, D[_]](list: D[Reader[C, R]])(implicit canMap: CanMap[Reader[C, R], R, D]): Reader[C, D[R]] = reader { conn =>
   canMap.map(list) { r: Reader[C, R] =>
      r(conn)
   }
}

It does look a bit different from our first implementation. To start with, in addition to the type parameters of the reader (C the dependency and R the result type), it takes a third parameter D which is the generic type of our wrapper (which could be an Option or a Future, etc.).

The interesting part is how we tell scala that this type D should follow the trait CanMap.
As I said earlier, we cannot add CanMap as a superclass of Option, so what we do, it to tell the compiler to look in the context for an implementation of CanMap that is applicable to this type: (implicit canMap: CanMap[Reader[C, R], R, D]).

For scala to find this in the implicit context, we need to slightly change our previous declaration of OptCan to be implicit:


implicit def canmapopt[A, B] = new CanMap[A, B, Option] {
   def map(l: Option[A])(f: A => B): Option[B] = l.map(f)
   def flatMap(l: Option[A])(f: A => Option[B]): Option[B] = l.flatMap(f)
}

We can now write a call to the sequence function:


val read: Option[Reader[Int, Int]] = Some(reader { c: Int => c*2 })
val move: Reader[Int, Option[Int]] = Reader.sequence(read)

No need to pass in the implicit CanMap as the compiler will find it automatically based on the surronging types of the function call. Because we user an Option[Reader[Int, Int]], scala knows that it has to look for an implementation of CanMap[Int, Int, Option] which is provided by our implicit definition.

If we want the sequence function to work with Future, the only thing that we need to do know is to add a new implicit implementation of CanMap:


implicit def canmapfuture[A, B](implicit ex: ExecutionContext) = new CanMap[A, B, Future] {
  def map(l: Future[A])(f: A => B): Future[B] = l.map(f)
  def flatMap(l: Future[A])(f: A => Future[B]): Future[B] = l.flatMap(f)
}

This one is again pretty trivial, except that we need to have in the scope an implicit ExecutionContext so that scala knows where the future computations are being pooled.

We can now use the same type of call to move a future:


val read: Future[Reader[Int, Int]] = Future.successful(reader { c: Int => c*2 })
val move: Reader[Int, Future[Int]] = Reader.sequence(read)

This is pretty neet, the sequence function is now generic and can be applied to any type for which we can implement a CanMap typeclass. As you can see, CanMap is a way to describe a behaviour of a class without messing with its type hierarchy, it's a pretty powerful tool to extend existing libraries or to wrap Java libraries in nice scala syntax.

You might think that this is a lot of scafolding code for such a simple function, but as we'll see in the next post, it's a very usefull typeclass and it actually makes the Reader's code more reusable and makes the use of Readers in the rest of your code cleaner.

Traversable and CanBuildFrom

But what about implementing CanMap for Traversable? This is a bit more complex due to the structure of the Collection implementation in the scala libraries. Since scala 2.8, the collection API is structured in a very (smart) generic fashion, whish is quite complex to understand at first. However, once you understand what typeclasses are, it's not so complicated.

To build the CanMap for Traversables, we need to first understand what CanBuildFrom does. If we look at the (real) signature of map and flatMap in the Traversable trait:


def flatMap[B, That](f: (A) ⇒ GenTraversableOnce[B])(implicit bf: CanBuildFrom[Traversable[A], B, That]): That

def map[B, That](f: (A) ⇒ B)(implicit bf: CanBuildFrom[Traversable[A], B, That]): That

It's not very straightforward, there are two strange things:

a type That, which is the type of the new collection returned by the map
an implicit CanBuildFrom

If you understood the principle of typeclasses, you will have identified this implicit CanBuildFrom as a typeclass. In fact, this typeclass is a way to define methods to build new traversables, without having to define all the possible traversables that can be built a priori.

But why do you need this?

Imagine a naive signature of map in Traversable:


def map[B](f: A => B): Traversable[B]

This will always return a type of Traversable when you call map on a subclass of this trait. This is not very practical, imagine that you have a Set, when you apply map you would like it to return a Set, and not a Traversable. You could write a custom map within each collection that returns the same type as your collection. But imagine a specialised set like BitSet, which is optimized to store non negative integers. If you called myBitSet.map((a: Int) => "elt: "+i), you cannot return a BitSet as you would have a collection of String.

CanBuildFrom is there to help, it allows scala to choose the best type possible of the returned collection, based on the available implementation of this typeclass that are currently in scope. CanBuildFrom[Traversable[A], B, That] then explains to scala how to build a new collection of type That (Set[String] for instance) from the current traversable.

So, in our implementation of CanMap for Traversable, we have to keep such feature and make sure that we have the right CanBuildFrom in the scope of our typeclass.

Here is how it is done (thanks to a stackoverflow answer):


implicit def canmaptrav[A, B, M[+_]](implicit bf: CanBuildFrom[M[A], B, M[B]], ev: M[A] => TraversableLike[A, M[A]], eb: M[B] => TraversableLike[B, M[B]]) = new CanMap[A, B, M] {
    def map(l: M[A])(f: (A) => B): M[B] = l.map(f)
    def flatMap(l: M[A])(f: A => M[B]): M[B] = l.flatMap[B, M[B]] { (a: A) => f(a) }
}

The implementations of map and flatMap are pretty much identical to the ones for Option or Future. The difference is that we put three implicits in the context:

CanBuildFrom[M[A], B, M[B]] tells scala how to build collections containing B from a collection of type A. This is needed by the map function to build the new collection with the changed type.
M[B] => TraversableLike[…] are implicit conversions to convert our container type M in valid TraversableLike types. This is a way to tell scala that we are only working on types that can be converted to traversables, even if they are under not within traversable type hierarchy to start with.

It's all done, we can now make a call to sequence in the following manner:


val reader: Seq[Reader[Int, Int]] = Seq(reader { c: Int => 10 }, reader { c: Int => 20 })
Reader.sequence(reader)

A Final Note

You can find the implementation of CanMap and Reader in the following gist.

If you are used to functional programming, you will have noticed that our typeclass CanMap actually describes something very similar to a Monad. In fact, scalaz provides a more complete implementation of this typeclass, and if you dare, you can go look in the Functor and Monad typeclasses provided by this library.

In the next post, I will show how we can keep generarilizing the tooling provided in the previous post by using this CanMap typeclass.