Last Updated: February 25, 2016
·
8.323K
· mortimerpa

Curry and Cake without type indigestion -- Covariance, Contravariance and the Reader Monad

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:

  1. Dependency Injection for Configuring Play Framework Database Connection(s) part 1
  2. Dependency Injection for Configuring Play Framework Database Connection(s) part 2
  3. Curry and Cake without type indigestion -- Covariance, Contravariance and the Reader Monad
  4. Tooling the Reader Monad
  5. Generalizing the Reader Tooling, part 1
  6. Generalizing the Reader Tooling, part 2

In my two pervious posts, I have talked about using different injection techniques to configure data sources in Play!, while the examples were based on that framework, they can be used in any other scala project. In this post I will keep on the topic of the last post: the use of the Reader Monad and the Cake Pattern, but without using specifics from Play!.

Reader monad for injecting Data sources (and other interchangeable components)

If you don't have time to read the two last posts, then here is a short summary, if you have just read them, you can just read this quickly for a refresh.

The problem I have been discussing is the one of configuring data sources, such as databases, without having deep dependencies in your code to a particular implementation. Imagine for instance that you have a blogging platform and that you are using MySQL to store information about your Users and their Posts, you then realize that Posts are pretty static and you don't need to do complex queries to retrieve them (i.e. you just need to list all the posts from a particular user), you might want to move this part of your system to a document based database, such as mongoDB or couchDB. If you haven't been too careful with your data store connection implementation, you have mySQL queries lurking here and there in your code, mixing Users and Posts at the code level and the SQL level.

The first step I proposed in the previous post was to use the cake pattern to separate the connection logic from the business logic. This involves creating interfaces (trait) that represents operations on your data sources, on for each separable source. In our example, this is a connection for the users' data source and one for the posts' one:

trait UserConnection {
    def readUser(id: Long): Option[User]
    ….
}
trait PostConnection {
    def readPosts(user: User): Seq[Post]
}

This is a simplified code, but you get the idea. Then you can have specific implementation for these:

class MySQLConnection extends UserConnection { … }
class MongoConnection extends PostConnection { … }

This is also simplify the testing as you can implement mocks of particular bit of the connection.

The second issue that I discussed was the one of injecting the right implementation in the methods that are using these connections. The proposed idea was to avoid implicit and use currying instead. This means that instead of returning a result when calling a method depending on a connection, you return a function which takes as parameter the dependency and will eventually return the result:

def userPosts(userID: Long): UserConnection with PostConnection => Seq[Post] = conn => {
     (conn.readUser(userID) map { user =>
         conn.readPosts(user)
     }) getOrElse(List()) //getting rid of the Option just to simplify the code in this article
}

You will agree that this is ugly to read, and when you want to compose different calls, you end up having a lurking conn in your code that is not straightforward to follow and grasp for newcomers. This is where the Reader Monad comes in; I know I have said monad, but don't worry, it's not that bad.

The Reader monad is a wrapper around a function (e.g. Connection => Future[Iterable[Post]]) that can be transformed with map and composed with flatMap as you would do for Future or a collection like List. If you don't have a general idea of what these two functions do, check out the previous and go read an intro on them. A naive code for the Reader monad is given in the previous post and I will discuss it later on.

If you often use UserConnection with PostConnection, you can also simplify the signature by defining our composed connection somewhere in the code:

type UserPostConn = UserConnection with PostConnection

so our function signature now becomes:

def userPosts(userID: Long): Reader[UserPostConn, Seq[Post]]

We could then use map to transform what's in the Reader, for instance, to get only the titles of the posts:

val titlesReader: Reader[UserPostConn, Seq[String]] = userPosts(id).map { postIterable =>
   postIterable.map(_.title)
}

In this example, we get the iterable inside the reader and we extract the title of each item.

Type Covariance

In the previous post, I gave this simple implementation of a Reader:

object Reader {

  implicit def reader[From, To](f: From => To) = Reader(f)

  def pure[From, To](a: To) = Reader((c: From) => a)

}

case class Reader[From, To](wrappedF: From => To) {

    def apply(c: From) = wrappedF(c)

    def map[Tob](transformF: To => Tob): Reader[From, Tob] =
      Reader(c => transformF(wrappedF(c)))

    def flatMap[Tob](transformF: To => Reader[From, Tob]): Reader[From, Tob] =
      Reader(c => transformF(wrappedF(c))(c))

}

Reader takes two type parameters, the type of the dependency From (the connection in our case) and the type of the value that you will get once you resolve the dependency To.

The first issue you will get to, even if scala is very smart about it in most cases, is that of upcasting to a reader with a more general return type To. Something like this:

val posts: Reader[UserPostConn, Iterable[Posts]] = userPosts(10l)

will not compile. This is because the To type of the returned reader is a Seq and scala is expecting a Iterable. Even if Iterable is an ancestor of Seq, scala doesn't really know what to do unless you tell him explicitelly.

This is what type covariance is for, it allows you to say that Reader[_, Seq[_]] can be used in place of Reader[_, Iterable[_]] as you can use Seq in place of Iterable, because it is lower in the class hierarchy. The only thing we have to do for scala to infer this, is to annotate Reader properly:

case class Reader[From, +To](wrappedF: From => To)

The + tells the compiler that Reader is "covariant" for the parameter type T. For java programmers, it's a bit hard to understand at first, but try the example above, with and without the + annotation. You can find the code for this in this gist. Just open a worksheet with it and you will see the results.

Type Contravariance

Covariant generic types make sense prety quickly, it seems natural that a type wrapping another type follows the same type hierarchy as the type it embeds. However, this is not always the case, and there is the inverse type of relation: contravariance.

A contravariant type annotation tells the compiler that a type A[B] can be used in place of A[C] if B can be used in place of C. This sounds totally counterintuitive and you have to read it a couple of time just to get what it means. The Reader monad that we are studying provides us with a good example of where contravariance is needed.

First, let's start by making a small utility function, which I already mentioned in the previous post, to simplify the use of a Reader.

When you want to get a reader's value, you need to call apply on it, passing a concrete dependency. Something like this:

val postReader = userPosts(10l)

class RealConnection extends UserConnection with PostConnection

val conn = new RealConnection

val actualPosts = postReader(conn)

This is a bit cumbersome and not always very readable for others. We can define a nice little utility that will take care of unwrapping the reader:

def withDependency[F, T](dep: F)(reader: Reader[F, T]): T = reader(dep)

We can then write

val actualPosts = withDependency(new RealConnection) {
  …
  userPosts(10l)
}

You will eventually have a large block of code, where you compose different readers together, and that you eventually pass into the withDependency. Ideally somewhere at the top of your application data flow.

However, if you try this, the compiler will spit out an error that the returned type of userPosts is not compatible with the type expected by withDependency. In fact the function returns a Reader[UserConnection with PostConnection, _] while we are expecting a block of type Reader[RealConnection, _].

However, RealConnection does implement everything you want from a UserConnection with PostConnection, it's a concrete subtype of this interface. So you can effectivelly use anything that is a UserConnection with PostConnection when you have a RealConnection. But you need to tell the compiler that Reader[RealConnection, _] can be used where you have a Reader[UserConnection with PostConnection, _] so that you can upcast the result of userPosts to the type expected by withDependency.

In scala, this is annotated in your code with -:

case class Reader[-From, +To](wrappedF: From => To)

However, marking From as being contravariant will create a new problem. The flatMap function will not compile, giving you the error:

contravariant type From occurs in covariant position in type To => test.Reader[From,Tob] of value transformF

This is because you cannot use a contravariant type parameter as a result type, you can only use it as a parameter type of a function. This stackoverflow answer provides some details of why this is.

We need to make the flatMap method parametric on this return type so that it is not contravariant:

def flatMap[FromB <: From, ToB](f: To => Reader[FromB, ToB]): Reader[FromB, ToB] =
     Reader(c => f(wrappedF(c))(c))

We are using a trick, saying that the result type is Reader[FromB, ToB] where we scope FromB as a subtype of our contravariant type.

The Reader class is now pretty much usable:

case class Reader[-From, +To](wrappedF: From => To) {

  def apply(c: From) = wrappedF(c)

  def map[ToB](transformF: To => ToB): Reader[From, ToB] =
    Reader(c => transformF(wrappedF(c)))

  def flatMap[FromB <: From, ToB](f: To => Reader[FromB, ToB]): Reader[FromB, ToB] =
    Reader(c => f(wrappedF(c))(c))

}

You can find this class and examples in the following gist, again, you can save it as a worksheet and experiment with it.