Theory

ReaderT for safely converting Future-based traits to cats-effect

Preface

Writing service interfaces is a popular way to logically seperate sections of code for good reason: It makes code more manageable. You have probably come across these services no matter what language you have used. Let's look at a simple example of a service implemented in scala with a trait: (Footnote: We use traits to define the service because we want to seperate the implementation from the interface. This makes refactoring and maintaining easier)

trait UserRepo {
  def getUser(userId: Int): User
  def addUser(user: User): Int
  def deleteUser(userId: Int): Unit
}

These services can often involve accessing a database, issuing an http request, or writing to the file system. These operations tend to take time, but the methods of this service don't reflect that. So the first way we dealt with this is the scala.concurrent.Future.

trait UserRepo {
  def getUser(userId: Int): Future[User]
  def addUser(user: User): Future[Int]
  def deleteUser(userId: Int): Future[Unit]
}

You can tell from the type itself now: these are operations that take time, and may even fail. This makes it easier to write code that can execute concurrently, and that handles failure well.

Future is not quite the end of the story though... There is one thing that is not ideal about the Future: it breaks referential transparency (in other words: it executes when you define it as opposed to when you use it). I'll avoid going too far into what this is and why it is a bad thing, but if you're curious you can check out this article that explains it pretty well.

Avoiding Futures

It's not uncommon to run into a service that uses Future. Perhaps the implementation was automatically generated by a tool like Twitter Scrooge, or your codebase hasn't been converted to something else yet. Whatever the case is, we would like to change them to use a type that is more well-behaved.

We want to define a service without being directly tied to the implementation of Future. Types like Future that attempt to contain side-effects and encourage dealing with failure proactively are generally called effect monads or effect types. (Footnote: That may not be the dictionary definition, but it is practical for our purposes. If you would like to know more about effect monads you can read up on them here). Thankfully, scala has a way to define a service without defining the precise effect monad:

trait UserRepo[F[_]] {
  def getUser(userId: Int): F[User]
  def addUser(user: User): F[Int]
  def deleteUser(userId: Int): F[Unit]
}

(Note: Theoretically you could put any type constructor in place of F. Like UserRepo[List], UserRepo[Option], or UserRepo[Function0])

One of the most common effect monads to use is cats.effect.IO, but there are others that are popular as well like monix.Task and zio.ZIO. So now the question becomes: how do we choose which effect to use? and how do we make the switch? It turns out we can cheat: We don't need to choose an effect type at all! (at least not yet) With a clever trick, we can write code that will work with almost any effect monad. First, consider a service that is already implemented with Futures:

class FutureUserRepo extends UserRepo[Future] {
  override def getUser(userId: Int): Future[User] = ???
  override def addUser(user: User): Future[Int] = ???
  override def deleteUser(userId: Int): Future[Unit] = ???
}

Using the nifty function IO.fromFuture allows us to easily define an UserRepo[IO] service using the UserRepo[Future]:

def liftUserRepoToIO(futRepo: UserRepo[Future]): UserRepo[IO] =
  new UserRepo[IO] {
    override def getUser(userId: Int): IO[User] = IO.fromFuture(IO(futRep.getUser(userId)))
    override def addUser(user: User): IO[Int] = IO.fromFuture(IO(futRep.addUser(user)))
    override def deleteUser(userId: Int): IO[Unit] = IO.fromFuture(IO(futRep.deleteUser(userId)))
  }

Other effect monads usually have their own version of IO.fromFuture, so we can instead use a cats typeclass to ensure that our chosen effect monad can lift Futures. We can accomplish that with the cats.effect.Async typeclass. We use the typeclass by requiring an implicit parameter of the right type. So rather than directly using IO we can write:

def liftUserRepoToF[F[_]](futRepo: UserRepo[Future])(implicit a: Async[F]): UserRepo[F] =
  new UserRepo[F] {
    override def getUser(userId: Int): F[User] = a.fromFuture(a.delay(futRep.getUser(userId)))
    override def addUser(user: User): F[Int] = a.fromFuture(a.delay(futRep.addUser(user)))
    override def deleteUser(userId: Int): F[Unit] = a.fromFuture(a.delay(futRep.deleteUser(userId)))
  }

(Most monads will have an implementation of Async, usually in a package dedicated to cats-effect interoperability. For example, zio has zio.interop.cats) The style above is easiest to read if you are not familiar with this style; The implicit import is written out explicitly and used by referencing its name. There is an equivalent way to write it that is more common:

def liftUserRepoToF[F[_]: Async](futRepo: UserRepo[Future]): UserRepo[F] =
  new UserRepo[F] {
    override def getUser(userId: Int): F[User] = Async[F].fromFuture(Async[F].delay(futRep.getUser(userId)))
    override def addUser(user: User): F[Int] = Async[F].fromFuture(Async[F].delay(futRep.addUser(user)))
    override def deleteUser(userId: Int): F[Unit] = Async[F].fromFuture(Async[F].delay(futRep.deleteUser(userId)))
  }

This version uses context bound syntax, and it is exactly equivalent to the previous example except the implicit Async[F] no longer has a name, so we cant call it directly. We have to use Async.apply[F] which is basically the same as implicitly:Async[F] (i.e. it's just grabbing the implicit Async[F] without needing to use its name)

If you would like to learn more about this style of writing services, it is generally referred to as final tagless or tagless final. Why is it called that? It's complicated, but first it might be more helpful if we explore why you should be using it

Now we have a way to rewrite our Future services safely in any effect monad we want! But that's not good enough! Here we run into the eternal struggle of programmers: is there a simpler way to do all of this? Currently we basically need to rewrite the entire service with Async.delay and Async.fromFuture, but we're basically writing the same exact thing for each method. Intuitively it feels like we should be able to capture the basic idea of translating Future => F. Then once we have something like that, we can make a function that will translate the service for us:

def liftK[F[_]: Async](transform: Future => F)(s: Service[Future]): Service[F]

We will come back to why we have called it liftK, for now we have to figure out how to make transform. A good first attempt might look something like:

def transform[F[_]: Async]: Future => F = 
  (f: Future) => Async[F].fromFuture(Async[F].delay(f))

Unfortunately for us, Future => F is not valid scala. Both Future and F are not types by themselves, they are type constructors. If we wanted to use => we need to add a type inside Future and F like this:

def transform[F[_]: Async, A]: Future[A] => F[A] = 
  (f: Future[A]) => Async[F].fromFuture(Async[F].delay(f))

We've got something that should at least compile now, but if you look carefully, you'll see why this wont be useful. We'll try using it in our original liftK:

def liftK[F[_]: Async, A](transform: Future[A] => F[A])(s: Service[Future]): Service[F]

Our problem is that now we have a function liftK[F, A] that must have a concrete A type. That means that this liftK function will only be able to lift values of Future[A], so if we have a service that has different return types you would a liftK for every type!

Future[A] => F[A] can be interpreted as "A transformation that converts a Future into an F for one concrete type", but what we really need is "A transformation that converts a Future into an F regardless of the type inside". Some of the more experienced scala devs might interject: "Why not take advantage of subtyping and use Any to make a Future[Any] => F[Any]? That could be applied to any concrete type!". That is indeed true, you can do that. The problem is this would require runtime casting an Any to some concrete type every time we want to use it. This doesn't seem like a big deal, but the tagless part of tagless final is referring to the fact that we don't require runtime casts! so we cant do that.

Some of the even more experienced functional programmers may be asking why can't we use an existential type? I must concede I do think that should be possible, but I've not worked with existential types in scala very much. I'll leave it as an exercise to the reader to try to get everything working with a custom:

type FunctionK[F[_], G[_]] = F[a] => G[a] forSome {type a}

A Better Way

Thankfully for us, cats once again has the solution: FunctionK.

trait FunctionK[F[_], G[_]] {  
  def apply[A](fa: F[A]): G[A]
}

It can also be written as F ~> G. You may also hear this called a natural transformation. Where a normal Function1 transforms between types, FunctionK transforms between type constructors. You might hear someone say something to the effect of "FunctionK is just a higher-kinded function" or maybe "FunctionK operates on higher-kinded types". If you are unfamiliar or uncomfortable with this term, don't fret. Here is an excellent description of kinds. It is useful to note that when dealing with higher-kinded types in cats, it is usually named after the lower-kinded equivalent with a K tacked onto the end. Hence we have Function1[A,B] turning into FunctionK[F[_], G[_]].

Now we can revisit our liftK function to see what we're missing:

def liftK[F[_]: Async](transform: Future ~> F)(s: Service[Future]): Service[F]

Now that both of the parameters are making sense, we must start thinking about how we might actually implement it. All we need to construct is something like Service[Future] => Service[F]. Before we actually try to make this function, it will be useful for us to look at the general "shape" of the function.

Service[Future] => Service[F]

It may not look familiar yet, so let's look at a similar structure:

List[Int] => List[String]

what kind of function would you use to make something with this type?

...

That's right! It's our good old friend list.map!

If you are accustomed to cats, you will know that there is a typeclass that generalizes the idea of maping: the Functor.

So if we can make an instance of Functor[Service] for our service, then we can simply use map to change between Future and F.

Unfortunately, it's not that easy. In the List example, List[A] is a type constructor that takes the type A, but our Service is a type constructor Service[F[_]] that takes in the type constructor F[_], so we can't simply make a Functor[Service]. We are forced to instead make a Functor[Service[_[A]]], and we run into the same problem that we did with Future => F. If you were attentive, you might have guessed the solution already: we instead need to make an instance of FunctorK[Service], and rather than implementing the function map we will be making the function mapK. Seeing the typeclass definitions might help get across what the relationship is:

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

trait FunctorK[A[_[_]]] {
  def mapK[F[_], G[_]](af: A[F])(fk: F ~> G): A[G]
}

Now let's do an implementation for our UserRepo:

class UserRepoFunctorK extends FunctorK[UserRepo] {
  override def mapK[F[_], G[_]](repo: UserRepo[F])(fk: F ~> G): UserRepo[G] =
    new UserRepo[G] {
      override def getUser(userId: Int): G[User] = fk(repo.getUser(userId))
      override def addUser(user: User): F[Int] = fk(repo.addUser(user))
      override def deleteUser(userId: Int): F[Unit] = fk(repo.deleteUser(userId))
    }
}

Now we can finally implement our liftK!

def liftK[F[_]: Async](transform: Future ~> F)(s: Service[Future])(
                                                implicit functorK: FunctorK[Service]
  ): Service[F] = functork.mapk(s)(transform)

Now you might be wondering: "How does this reduce boilerplate when compared to the previous solution? you still need reimplement service in the definition of FunctorK!". You have a point, but it turns out we dont actually need to implement the FunctorK instance ourselves. The cats.tagless.Derive.functorK macro can generate the code so we dont have to! Overall, our service definition has been cleaned up to this:

trait UserRepo[F[_]] {
  def getUser(userId: Int): F[User]
  def addUser(user: User): F[Int]
  def deleteUser(userId: Int): F[Unit]
}

object UserRepo {
  val functorK: FunctorK[UserRepo] = Derive.functorK

  //allows us to call UserRepo[F] to summon the service if it exists in implicit scope
  //e.g. UserRepo[F].getUser(user) is really UserRepo.apply[F].getUser(user)
  def apply[F[_]](implicit repo: UserRepo[F]): UserRepo[F] = implicitly

  def liftK[F[_]: Async](repo: UserRepo[Future])(transform: Future ~> F): UserRepo[F] =
    functorK.mapK(repo)(transform)
}

Now all we need is an implementation of Future ~> F and we're done!

def futureToF[F[_] : Async](implicit ec: ExecutionContext): Future ~> F =
  λ[Future ~> F] { 
    (fut: Future[α] forSome {type α}) => 
      Async[F].fromFuture(Sync[F].delay(fut))  
  }

The λ syntax is from the compiler flag for higher-kinded types.

The False Prophet

Now we have a nice neat way to translate our Future services to a more well behaved effect like IO. We should test a simple example:

trait FooService[F[_]] {
  def foo(s: String): F[Unit]
}

object FooService {
  val functorK: FunctorK[FooService] = Derive.functorK

  def apply[F[_]](implicit f: FooService[F]): FooService[F] = f

  def liftK[F[_]: Async](s: FooService[Future])(nt: Future ~> F): FooService[F] = 
    functork.mapK(s)(nt)
}

and an implementation in Future:

val futureService: FooService[Future] =
  new FooService[Future] {  
    def foo(s: String): Future[Unit] = Future(println(s))
  }

val ioService: FooService[IO] = FooService.liftK[IO](futureService)(futureToF)

For comparison we show why the Future is poorly behaved:

val foo1 = futureService.foo("first")
val foo3 = futureService.foo("third")
val foo2 = futureService.foo("second")

for {
  _ <- foo1
  _ <- foo2
  _ <- foo3
  _ <- foo3
} yield {}

Console shows output:

first
third
second

The Futures execute in the order that they were defined, not the order that they are combined. They also memoize results, so calling foo3 twice will not end up printing after the definition. Of course, our beloved IO implementation doesn't have these nasty properties:

  val foo1 = ioService.foo("first")
  val foo3 = ioService.foo("third")
  val foo2 = ioService.foo("second")

  (for {
    _ <- foo1
    _ <- foo2
    _ <- foo3
    _ <- foo3
  } yield {}).unsafeRunSync()

Console shows output:

first
third
second

As we can see IO is much superi...

wait

But it should be...

...

Okay, so after all of that work making an elegant and terse way to change effect types it didn't actually fix any of the problems with Future...

Wait, we can't get despondent yet! There has to be a way to fix this...

The Culprit

If you look very carefully, you can see what is going on:

trait FunctionK[F[_], G[_]] {  
  def apply[A](fa: F[A]): G[A]
}

If we substitute in the types that we used to make futureToF, it becomes:

trait FunctionK[Future, F] {  
  def apply[A](fa: Future[A]): F[A]
}

In our implementation we do specifically call:

Async[F].fromFuture(Sync[F].delay(fut))

Which would normally delay the execution of any computations happening in fut... or that would normally be the case, if we had defined the future inside that delay(). If we pass in a future that has already started computing, then delay wont do anything.

The culprit is none other that the definition of FunctionK.apply. The fa is strict, so no matter what implementation of FunctionK we can come up with, the Future will necessarily already be evaluated before being passed in and thus it will start executing before we can delay it.

The Clever Fix

This news is unfortunate, and it is where most hang up their hats and decide to deal with the boilerplate, but the cats-tagless devs are not most!

Georgi Krastev from the cats-tagless project suggested an alternative way.

A classic way to delay the execution of an expression in a language with first-class functions is to define the expression as the result of a function. By necessity, functions can't be evaluated before they have all of their arguments. An expression that has been delayed by an anonymous function in this way is called a "thunk". So if we were able to somehow make the result of all of the service methods into anonymous functions, then we could delay execution until we choose.

So if we were working on a FooService[F[_]], what would F[_] need to look like in order for us to be able to delay the Futures?... Like we said, it should be a function. The input should be something that we need in order to create the Future, and the result of the function should be the Future that we want to thunk. I will write the same type in a few different ways to help illuminate what it means:

  type F[A] = FooService[Future] => Future[A] 

  type F[A] = Function1[FooService[Future], Future[A]]

  type F = Function1[FooService[Future], Future[*]]

There is actually a typeclass that has this exact shape: ReaderT. Writing the same F in terms of ReaderT looks like:

type F[A] = ReaderT[Future, FooService[Future], A]

If we put that together to get the full type of the service we get:

FooService[ReaderT[Future, FooService[Future], *]]

FooService[FooService[Future] => Future[*]]

If we wanted to convert that type into a more understandable sentence, I would call it: a FooService where the result of each method is a recipie for how to get the result of that same method from the Future implementation. Like this:

class InjectedFooService extends FooService[ReaderT[Future, FooService[Future], *]] {
  override def foo(s: String): ReaderT[Future, FooService[Future], String] = ReaderT { 
      impl => impl.foo(i)  
  }
}

So we have effectively "factored out" the Future implementation.

Next we can define a natural transformation that can convert from this weird ReaderT monster to the monad that we want like this:

def provide[F[_] : Async, R](service: R): ReaderT[Future, R, *] ~> F =
  λ[ReaderT[Future, R, *] ~> F](r => Async[F].fromFuture(Async[F].delay(r(service))))

Notice that we now have Async[F].delay(r(service)) and remember that r has the type FooService[Future] => Future[*] and we are passing in the FooService[Future] which means that we are creating a Future. The only difference from the last time is that we were able to prevent the Future from being created before we could thunk it.

So we have fixed everything! right? Well we have the same problem with that initial service that we had with FunctorK[UserRepo]. We're not avoiding any boilerplate since we now have to make an implementation of this service:

FooService[ReaderT[Future, FooService[Future], *]]

Au contraire! It just so happens that the ReaderT is another thing that cats-tagless macros can generate!

We can derive the ReaderT implementation we called InjectedFooService above using cats.tagless.Derive.readerT. The FunctorK typeclass uses ~> instances to convert the effect type of traits like FooService.

In order to fully reduce boilerplate, we made provide more generic by partially applying the F[_] type and parameterizing the type of the provided service.

A full example can be found in examples