FunctionK

Some time ago at $WORK I encountered snippet like this:

def client(f: Request[Id] => HttpResponse[Id]): Client[SyncIO] =
  Client[SyncIO](r =>
    f(r.mapK(λ[SyncIO ~> Id](_.unsafeRunSync())))
      .mapK(λ[Id ~> SyncIO](SyncIO.pure(_)))
  )

It took me some time to understand it.

I mean, what’s the mapK, what’s that random λ symbol, and finally what is that ~> bit??

Times like these remind me that Scala can be a little bit cryptic too.

Nevertheless, let’s unpack it!

Types and Kinds

In Scala your function can have a type like this:

type Fn = Int => String
val fn: Fn = a => a.toString

That’s fine, but what if we want to create a function that accepts a generic param? In Scala 2 it was a little boilerplate-ish, but in Scala 3 we can use polymorphic function types:

type FnGen = [A] => A => A
val fnGen: FnGen = [A] => (a: A) => a

The [A] => part in the above function means that it accepts the type parameter A, and the A => A means that it accepts a concrete value of type A and returns a value of the same type A. In functional programming this is also known as an identity function.

With some external help in the form of the kind-projector compiler plugin, we can also get polymorphic function types in Scala 2. This is where this λ[F ~> G](...) from the original snippet comes from.

Let’s take this a step further with some type constructors:

type FunctionK[F[_],G[_]] = [A] => F[A] => G[A]

We have modified the FnGen example a little bit. Now it accepts the type constructors F and G as type parameters. Type constructors are types that accept type arguments, much like class constructors accept value arguments to create values. The [_] in both of our type constructors means that they require one type parameter. In F[A] and G[A] we apply the type parameter from the polymorphic function type to both F and G.

The K in FunctionK stands for kind, or higher kinded types (HKT). For now, you can think of them as holes in constructors. Types without holes could be thought of as 0-order kinds ( * ), types with 1 hole would be 1-order kinds (* -> *), 2 holes would mean 2-order kinds (* -> * -> *).

But what could these types represent in practice? Well, anything that matches following the signature, for example:

type VecToArr = [A] => Vector[A] => Array[A]

Funnily enough, the FunctionK described above is our ~>. Another mystery solved!

type ~>[F[_],G[_]] = FunctionK[F, G]

Yes, ~> is not a magic built-in operator. For better or worse, you can define infix methods and type constructors in Scala.

Using the ~>

FunctionK or ~> is useful whenever you want to write a function that is a general (or …natural 🙄) transformation from some F[_] to some G[_].

For example:

type EitherToOpt = ([X] =>> Either[?, X]) ~> Option
val eitherToOpt: EitherToOpt = [A] => (e: Either[?, A]) => e match
  case Left(_) => None
  case Right(value) => Some(value)

println(eitherToOpt(Left(1))) // None
println(eitherToOpt(Right(1))) // Some(1)

A couple of new things here.

The [X] =>> is a type lambda. Do not confuse it with the already mentioned polymorphic function type. Type is anonymous lambda is a function that operates on types. We need it because Either accepts two type parameters. We don’t care about the first one, so we use ?but we need the second one.

At some point in the future we will be able to write it like Either[?, _] ~> Option though.

~> in the wild

Now, let’s take a look at something a little bit more concrete.

trait Logger[F[_]]: 
  def log(msg: String): F[Unit]

  extension [F[_]](underlying: Logger[F])
    def mapK[G[_]](fn: FunctionK[F, G]): Logger[G] = msg => fn(underlying.log(msg))

In the snipped above we have defined a Logger trait with log abstract method and mapK extension method. Even thought we don’t know how to implement log yet, it doesn’t look too complicated, but what is mapK? The K parts seems suspicious, looks like we would be dealing with kinds again.

If you’ve ever used andThen, compose or map methods on Scala functions then you might notice that the signature of the mapK looks familiar:

type mapKLogger[F[_], G[_]] = Logger[F] => FunctionK[F, G] => Logger[G]
type ComposeK[F[_], G[_], H[_[_]]] = H[F] => FunctionK[F, G] => H[G] // The H looks weird because it's a type constructor that accepts a type constructor...

Yes, the mapK is just higher kinded function composition!

Moving on, let us define some helper classes

class Defer[A](action: => A):
  def run: A = action

given defLogger: Logger[Defer] = msg => Defer(println(msg))

Defer is a just a simple container for deferring code execution until the end of the program. We will use it to create an instance of Logger for it to defer printing values to the console. It’s declared with given instead of val so that mapK can correctly infer the instance. Explaining how it works is beyond the scope of this post, so let us ignore it for now.

val fnK: Defer ~> Defer = [A] => (df: Defer[A]) => Defer:
  println("called before")
  df.run

Now we define a concrete FunctionK instance from Defer to Defer which will prepend some side effects before running log.

The only thing left to do is to invoke our Logger instance and actually run the logger:

val logger = defLogger.mapK(fnK)

logger.log("Hello from logger").run 
// called before
// Hello from logger

The above example was rather trivial, but it showed how mapK could be used in modifying the effect type of our code. This technique might be useful in testing, when for example if you’d like to collect some data on every F[_] call.

Summary

Hopefully, by now we should have uncovered all, or at least most of the secrets of our original snippet and have learned a thing or two about functional programming concepts and Scala.