Nested types and function composition

In Scala and other typed functional languages – notably Haskell – monads are structures that allow the programmer to take a sequence of computations, each defined for a certain context, and chain them together in order to produce a single result at the end. For example, suppose you have to use an API that returns values inside the context of future executions. Something like this:

def getAddress(user: User): Future[Address]
def getGeolocation(address: Address): Future[LatLong]
def getCurrentWeather(coordinates: LatLong): Future[WeatherDetails]    

Given a certain user, we would like to use this API to find out the current weather conditions at the location where he lives. So we can write a method like:

def usersWeather(user: User): Future[WeatherDetails] = {
  for {
    address <- getAddress(user)
    coordinates <- getGeolocation(address)
    weather <- getCurrentWeather(coordinates)
  } yield weather
}

Pretty straightforward. In each generator, the value “inside” the Future is supplied as input to the next method in the sequence. Now suppose you were given a more complex API, in which the computations are wrapped inside a context of future execution which may or may not contain a value. In other words, all methods return Future[Option[T]], for some type T. So, the methods above would become:

def getAddress(user: User): Future[Option[Address]]
def getGeolocation(address: Address): Future[Option[LatLong]]
def getCurrentWeather(coordinates: LatLong): Future[Option[WeatherDetails]]

In this case, it is not possible use our good old friend flatMap anymore. At least not directly, as in the first case. You cannot supply the value of each Future to the next function in the sequence because none of these methods accept an Option[T] as input. One possible solution to this problem is to convert these functions to other functions, lifting only their domain from A to Option[A]:

def convert[A, B](f: A => Future[Option[B]]): Option[A] => Future[Option[B]] = {
  maybeA => maybeA map f getOrElse Future(None)
}

which would allow us to put the functions back in shape to be used in a for comprehension:

for {
  address <- convert(getAddress)(user)
  coordinates <- convert(getGeolocation)(address)
  weather <- convert(getCurrentWeather)(coordinates)
} yield weather

But we are looking for a more elegant and more general solution, which could work for a whole family of types. If, instead of Option, for example, we had List or Either, we would need customized versions of convert for each of these types. With the aid of typeclasses, however, we can write a single function that allow us to compose these kinds of functions in a simple and concise way.

A word about typeclasses

In the beginning of this article, I talked about how monads allow the programmer to chain a sequence of computations inside a context. But what we actually did was using a for comprehension, which is a syntax sugar for classes that implement the methods map, flatMap, filter and foreach.

Scalaz, on the other hand, is an awesome library, written in Scala, that provides a broad array of bona fide typeclasses. In particular, Scalaz provides a Monad[F[_]] typeclass, which is going to be the most important piece in our solution to composition of functions with nested types.

So, let’s get to it. First of all, we need to define an instance of scalaz.Monad for the Future type:

val futureMonad = new Monad[Future] {
  override def point[A](a: => A): Future[A] = Future(a)

  override def bind[A, B](fa: Future[A])(f: A => Future[B]): Future[B] =
    fa.flatMap(f)
}

Strictly speaking, this implementation is not a monad, since it violates the law of left identity, which states that futureMonad.point(a) bind f should be equal to f(a). While in most cases, this equality relation holds, there is a special case for which it is false. For the sake of robustness, the designers of Scala chose to implement Future.flatMap so that it does not throw exceptions, even if the function that was passed as a parameter to it does. So, in the presence of exceptions, this law is broken. But for most practical purposes, this is not important and we can still think of it as a monad.

The Option type, on the other hand, is way less controversial. Scalaz defines monad instances for it, which can be readily made available to an application with an import. So we are not going to spend time talking about this particular monad. Option is also an instance of the Traverse typeclass. In the Haskell documentation (in which most of scalaz was inspired), Traverse is defined as a “class of data structures that can be traversed from left to right, performing an action on each element.” The importance of this will become clear in a bit.

Composing the functions

So, with this typeclass arsenal, we can start solving our composition problem. But first, let’s state clearly what exactly is the problem and what we aim to achieve. Given two functions, f: A => Future[Option[B]] and g: B => Future[Option[C]], we would like to define a higher-order function that takes f and g and produces a new function of type A => Future[Option[C]]. More formally – and more generically – we need a function composeN of the following type:

composeN[A, B, C, F[_], G[_]](f: A => F[G[B]], g: B => F[G[C]]): A => F[G[C]]

Taking advantage of the richness of Scala’s type system, let’s start by reasoning about the types and what transformations we would need. Observe that both f and composeN are functions from A to F (of something). This sounds like monad binding. So, let’s assume we have an implicit value of type Monad[F] in scope. The implementation of the method would have the form of:

a => fMonad.bind(f(a)) {
  gb => ...
}

The value gb above is of type G[B]. Assuming that we also have an implicit Monad[G] in scope, we could map over gbwith the function g:

val gfgc: G[F[G[C]]] = gMonad.map(gb)(g)

which results in a value of type G[F[G[C]]]. Note how the type G appears twice in the type declaration. That’s one time too many and we need to get rid of this extra G. But before that, let’s make one further assumption: that there is an implicit Traverse[G] in scope. This would allow us to use the sequence function of monads to swap the outermost G and the F:

val fggc: F[G[G[C]]] = fMonad.sequence(gfgc)

The last transformation is the one that will take us where we want:

val fgc: F[G[C]] = fMonad.map(fggc)(ggc => gMonad.bind(ggc)(identity))

So, the complete definition of the function is as follows:

def composeN[A, B, C, F[_], G[_]](f: A => F[G[B]], g: B => F[G[C]]): A => F[G[C]] =
  a => fMonad.bind(f(a)) {
    gb => fMonad.map(fMonad.sequence(gMonad.map(gb)(g))) {
      ggc => gMonad.bind(ggc)(identity)
    }
  }
}

Finally, in order to provide a syntax sugar and make the code look cleaner, we can wrap the first function inside a class (I called it ComposeNested, but I’m sure there is a much better name for this) and expose a method to be used as infix operator:

class ComposeNested[A, B, F[_], G[_]](f: A => F[G[B]])
          (implicit fMonad: Monad[F], gMonad: Monad[G], gTraverse: Traverse[G]) {

  def ->>[C](g: B => F[G[C]]): A => F[G[C]] = composeN(f, g)

  private def composeN[C](f: A => F[G[B]], g: B => F[G[C]]): A => F[G[C]] = ...

Back to our original example: how can we compose those three functions, chaining the computation through them in a specified order, while preserving their semantics while reducing (or rather hiding) the code noise? Let’s use the operator ->> we just defined:

object Demo extends App {
  val usersWeather = getAddress ->> getGeolocation ->> getCurrentWeather

  val futureWeather = usersWeather(User("John Doe"))

  futureWeather onFailure {
    case e: Exception => 
      println(s"Computation failed with the message: ${e.getMessage}")
  }

  futureWeather onSuccess {
    case result => println(s"Computation result: $result")
  }

  Thread.sleep(500)
}

The complete implementation can be found in my github repository.