# 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 A to C.

type Atype Btype Cval f: A => Bval 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 ScalatraitOptional[+A] {

defisValid: Boolean

defvalue : A

}case classPresent[+A](a:A)extendsOptional[A] {

override defisValid: Boolean =truevalue: A = a

override def

}case objectAbsentextendsOptional[Nothing] {

override defisValid: Boolean =falsevalue: Nothing =

override defthrow newNoSuchElementException

}

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.

defsafe_root_reciprocal: Double => Optional[Double] = {

importkleisliOptional._

valx =safe_root_

valy =safe_reciprocal_

x.>=>(y)

}safe_root_reciprocal(4) // returns Present(0.5)safe_root_reciprocal(-5) //returns Absentsafe_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]`

importcats.data.Kleisliimportcats.implicits._defsafeRootReciprocal(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 a`HttpService[F]`

is a simple alias for `Kleisli[F, Request, Response]`

. Monad transforms like `OptionT`

can also viewed as Kleisli.