Kleisli Category — From theory to Cats

Franck Mahon @ Flickr.com CC 2.0

Kleisli Category — the journey

From wikipedia.org

In category theory, a Kleisli category is a category naturally associated to any monad T

So far so good, but let’s break it down into pieces with a few examples on the way so we can go back to this sentence at the end of this post and understand exactly what it means.

Let’s suppose we want to handle the logs for our method executions so we can handle them as one single list of logs (by the way, the log example leading us to a category is borrowed from great video lecture series by Bartosz Milewski).

All the code samples are available in GitHub repository.

Solution 1

The simplest solution would be to store the logs in a global variable — I know, you have just shrugged but no worries, it’s just for demonstration purposes.

With logAcc as our log accumulator we can execute simple_1 and simple_2 functions and keep the logs nicely organized. But.. we all know it’s terrible and we all know that if you are reading this you want to see some functional way of solving things :)

Solution 2

The second approach — we pass the logs from one function execution to the next as a parameter:

This is better, the functions are pure and, at least, we know from the signature that the negating function does something else too. We can pass the second element of resulting tuple to the next function and have our concatenated log at the end. This of course is bad, the function uses some logic to handle logs inside which breaks single responsibility principle, and the function is difficult to memoize which should switch on a red light when thinking about pure functions. Let’s try something else..

Solution 3

We can decide to return a tuple like we did in the second example but we take just a Boolean parameter. We defer the log concatenation to the point where we call our functions:

Now, we have pure functions and some log ‘context’ we pass around and handle at the end. All is good, except the way we handle the resulting log, we need to keep the results from each execution, concatenate the logs etc., this can get difficult. In other words, we need a better way of composing those functions.

Solution 4

With function composition, we take two composable functions and create a single function out of it. If you are interested in Category Theory, you have probably already seen the example of composing function A -> B with function B -> C which results in function A -> C. Composition is fundamental to functional programming. Having three types A, B and C we can create our compose function like so:

The function above takes two functions as arguments and returns another function of type A to C.

With our Tuple example and ‘log context’ we can create our own composing function. The function will take two functions taking Boolean and returning (Boolean ,String ) and it will convert those to a single function which takes a Boolean and returns (Boolean ,String ). For this example I have generalized Boolean to a generic type A:

Please note that string concatenation operation is happening within our composition — composeT function. We know, by looking at our function that it’s a simple function composition and it’s associative, and having some knowledge about String, we know that composeT should be associative as String concatenation is associative.

If we have associativity, let’s check if we can create an identity. To create an identity function we need to have a function which will do nothing to our log. In other words we need a function which will take a Boolean and return the same Boolean value with an empty String as a tuple:

Easy!

Associativity? Identity? Does it ring any bells?

At this point we know we have associativity and identity — in other words we have a Category. In our Category the objects are Scala types and the arrows are A -> (B, String) (instead of simple A -> B arrows). The fact that the arrows are not simple transformation from A -> B makes them so called Kleisli arrows. Kleisli arrows can work with many different types, not only a tuple of some type B and String, they are defined for the types we impose as few conditions as possible, in other words for monadic types. This is where Cats definition of Kleisli comes in:

Kleisli enables composition of functions that return a monadic value, for instance an Option[Int] or a Either[String, List[Double]], without having functions take an Option or Either as a parameter, which can be strange and unwieldy.

So, how this is usefull?

Kleisli is all about composing. Let’s say we have a 3 functions we want to compose:

The simplest approach would be to call it one by one and pass the result from one to the other like so:

Or, you could just inline those calls like so:

In Scala we have functions like compose and andThen for doing just that:

The problem with all the above examples is that we need to match the inputs of one function with the outputs of another to make this all work. If some of the outputs will be a wrapper around some type (e.g. Future or Cats IO) we will get into trouble quickly.

Let’s wrap some values into something useful so we can see how you would typically handle that too:

Now it’s clear that we cannot just pass return value from generate to process etc. But we know that IO is a Monad and we can easily flatMap on it:

or with a cleaner approach — for comprehension:

With Kleisli we can do something similar but in many cases in more clear and readable way. Let’s start with the most verbose version:

Here, we wrap each function in Kleisli(..) type and then use the same andThen mechanism we have used with functions matching inputs and outputs (Side note: Cats library actually overrides Scala andThen and Scalaz uses andThenK for this purpose).

So far so good but we can do better :). There is an operator in Cats for working with Kleisli which you can use to get much cleaner code:

In addition, if you are using andThen approach, you don’t need to wrap in Kleisli all of the functions you want to use. The first one is enough, e.g:

I hope that throughout this tutorial you could see why Kleisli Category is a category naturally associated to any Monad T :). We went through a simple example with a tuple to get into Category and Kleisli arrows, and from that to the Cats library definition and usage.

Enjoy!