Category theory for Scala Programmers -Kleisli Categories

This post is an attempt to explain a “Kleisli” category in as simple way as possible. Many before have tried and some have succeeded.

A category consists of objects and arrows that go between them. These arrows compose such that if there is an arrow from A to B and another arrow from B to C, then there must be an arrow from A to C.

This is category theory 101. In Scala these objects are represented by types and the arrows are functions that are defined in these types. So, if we have three types A, B and C and there are functions going from A to B and from B to C.

type A
type B
type C
val f: A => B
val g: B => C

Then there must be a function from A to C as per category theory. And there is one that we can just write using f and g:

val gf : A => C = g compose f

How does this help us? Well this is basically function composition. The whole idea of making bigger programs from smaller , meaningful and easily comprehensible functions.

Now we move on to Kleisli’s . Kleisli categories are those that go from A to an F[B]. What the heck is an F here? Well F is a container for types and follows some laws. (Monad?). The reason they are so popular is because in functional programming languages like Scala we often come across functions that go from A to F[B] instead of A to B. Why ? because F describes an effect that helps us write pure code instead of impure

def divide(a: Double, b: Double): Double = {
  if(b==0) throw new IllegalArgumentException // not good

  a/b
}

def pureDivide(a: Double, b: Double): Either[String, Double] = {
  if(b==0) {
    Left("Error: attempt to divide by zero, this will be reported")
  }
  else {
    Right(a/b)
  }
}

Kleisli categories also provide support for composition. If we have an arrow from A to F[B] and an arrow from B to F[C] then there must exist an arrow from A to F[C]. Quoting an excerpt from Category Theory for Programmers by Bartosz Milewski

A Kleisli category has, as objects, the types of the underlying programming lan- guage. Morphisms from type 𝐴 to type 𝐵 are functions that go from 𝐴 to a type derived from 𝐵 using the particular embellishment. Each Kleisli category defines its own way of composing such morphisms, as well as the identity morphisms with respect to that composition.

Embellishment is another way of saying that the result is wrapped inside an F. So instead of A to B we have morphisms from A to F[B].

The author then defines an embellished type optional that denotes absence of value. The book presents a C++ version of optional type which we can define in Scala as below

// optional embellished type in Scala
trait Optional[+A] {

  def isValid: Boolean

  def value : A
}

case class Present[+A](a:A) extends Optional[A] {
  override def isValid: Boolean = true

  override def value: A = a
}

case object Absent extends Optional[Nothing] {
  override def isValid: Boolean = false

  override def value: Nothing = throw new NoSuchElementException
}

As an example, here’s the implementation of the embellished function safe_root:

def safe_root(x: Double): Optional[Double] = {
  if(x>=0) Present(Math.sqrt(x))
  else Absent
}

Challenge #1 : Construct the Kleisli category for optional/partial functions( define composition and identity)

object kleisliOptional {

  implicit class kleisliOptionalOps[A,B](m1: A => Optional[B]) {
    def >=>[C](m2: B => Optional[C]): A => Optional[C] = {
      a => {
        m1(a) match {
          case Present(value) => m2(value)
          case _ =>   Absent
        }
      }
    }

    def pure[A](x: A): Optional[A] = Present(x)
  }
}

Challenge #2: Implement the embellished function safe_reciprocal that returns a valid reciprocal of its argument, if it’s different from zero.

def safe_reciprocal(x: Double): Optional[Double] = {
  if(x!=0) Present(1/x)
  else Absent
}

Challenge #3: Compose safe_root and safe_reciprocal to implement safe_root_reciprocal that calculates sqrt(1/x) whenever possible.

def safe_root_reciprocal: Double => Optional[Double] = {
  import kleisliOptional._
  val x = safe_root _
  val y = safe_reciprocal _
  x.>=>(y)
}
safe_root_reciprocal(4) // returns Present(0.5)
safe_root_reciprocal(-5) //returns Absent
safe_root_reciprocal(0) //returns Absent

So now we have the power to compose Kleisli’s . This again goes a long way in writing bigger pieces of code from small chunks. And as you may have noticed the type Optional already exists in Scala in the form of Option. There are other embellished types like Either, Writer State that represent other use cases.

Now that we know how to write a Kleisli by our own , let’s look at whats already out there in the free world. A host of libraries like cats, scalaz define the Kleisli type and we do not need to write them for each new embellishment. We shall now use the cats library to compose functions that return a type embellished inside an Either.

def safeRoot(x: Double): Either[String, Double] = {
  if(x>=0) Right(Math.sqrt(x))
  else Left("Error: attempt to sqrt negative number")
}

def safeReciprocal(x: Double): Either[String, Double] = {
  if(x!=0) Right(1/x)
  else Left("Error: attempt to divide by zero")
}

To create a pipeline function that takes a Double and return the square root of its reciprocal (combines safeRoot and safeReciprocal) we can simply use the Kleisli type from cats.data

At its core, Kleisli[F[_], A, B] is just a wrapper around the function A => F[B]

import cats.data.Kleisli
import cats.implicits._
def safeRootReciprocal(x: Double): Either[String, Double] = {
  Kleisli(safeRoot).compose(Kleisli(safeReciprocal)).run(x)
}
safeRootReciprocal(4) // returns Right(0.5)
safeRootReciprocal(0) // returns Left(Error: attempt to divide by zero)
safeRootReciprocal(-5) //Left(Error: attempt to sqrt negative number)

As we can see above the cats library provides us the composition capability. We can compose other monadic types in a similar manner. run is the handler to the newly composed Kleisli.

So the next time you see a type that goes from A to F[B] just think Kleisli. They are ubiquitous in all popular functional libraries . In http4s aHttpService[F] is a simple alias for Kleisli[F, Request, Response] . Monad transforms like OptionT can also viewed as Kleisli.