Arrows, Monads and Kleisli — part I

During Scala Days Amsterdam I came across a concept of arrow. It was called a general interface to computation and it looked like a technique that could bridge code that is imperative in nature with proper functional programming. Later on I read about Railway Oriented Programming and found it really neat. I was compelled to reinvent the wheel and check all this in practice. I dug up some old business logic Scala code, that could really be Java code with slightly different keywords, and tried to refactor it using all I’d learned about arrows. BTW, you can find code used in this blog post on Github. In this post I’ll work with this code from the ground up and try to demonstrate curious things you can do with arrows. You can go through the examples by following commits in the GitHub repo.
Because no one in their sane mind likes to read “War and Peace”-sized posts, I decided to break it up into parts. In the first part I’ll explain arrows and Kleisli arrows, trying to show how they can help to express business logic in terms of data flow. In the next parts I’ll get into more complicated examples and, finally, introduce arrow transformers.

What’s an arrow?

In simple words arrow is a generalization of function i.e. it is an abstraction of things that behave like functions. Wikipedia says:

Arrows are a type class used in programming to describe computations in a pure and declarative fashion. First proposed by computer scientist John Hughes as a generalization of monads, arrows provide a referentially transparent way of expressing relationships between logical steps in a computation. Unlike monads, arrows don’t limit steps to having one and only one input.

Haskell wiki:

Arrow a b c represents a process that takes as input something of type b and outputs something of type c.

You can treat arrow as a function type that gives you more combinators to work with than function’s compose or andThen. Composing arrows is not only more expressive but can encapsulate rich semantics e.g. you can compose monadic processes.

Let’s get the party started

Let’s imagine we have legacy code pulled out of production tracking system. In this system things that are being tracked are modeled by a domain object called ProductionLot (simplified):

Code

You also have a repository for db access:

Business logic governing operations on production lots lies in, as you can imagine, ProductionLotsService. Let’s say you can perform three operations in this system. You can start production of a production lot, revoke production lot (change its current status and clear other properties) and reassign production lot to a different worker. Obviously these operations need to perform some kind of validations (eg. you cannot reassign production lot to the same worker it already has), interact with db etc.

Code

As you can see this code is littered with problems. First of all, it communicates with the outside world via exceptions. Clients of the service need to be better aware of that. Additionally, they can’t react to what is wrong as there is no distinction between various types of errors. Returning Unit does not make you a good neighbor either. All in all, API of this service is not very useful in the functional paradigm. Another problem is that it is quite hard to add new functionality. Imagine that there is a new requirement: production lot cannot be modified if its status has been set to done. You can’t help but grit your teeth and copy-paste this piece of logic through every method that updates production lots. Let’s try to improve this.
Our goal will be to eliminate problems we have observed and at the same time make this code functional. We’ll first attempt to refactor it so that adding our new requirement is a one liner and then try to eliminate exceptions, turning methods into pure functions.

Try function composition

As you probably noticed, all the methods follow the same pattern. Get something from db, validate the change, modify the entity and update db. This observation makes it appealing to try to rewrite it in function composition style. Of course, methods returning unit are not very composition-friendly, so a few adjustments have to be made, but you can write it arguably cleaner in the following way:

Code

This does not get us very far but you can observe an emerging pattern: every method can be rewritten as a composition over verify function and copy function plus a prologue and epilogue (find and save). verify and copy will be functions of ProductionLot and some environment (formed of arguments). This is a powerful insight yielding the idea on how to abstract out common behavior. I could be gluing functions together to get it done for now but, being aware of the ultimate goal of getting rid of exceptions, I’d rather embrace a more powerful abstraction of arrow.

Implement Arrow

What’s the interface of arrow? From Wikipedia

A type constructor arr that takes functions from any type s to another t, and lifts those functions into an arrow A between the two types

arr (s -> t) -> A s t

A piping method first that takes an arrow between two types and converts it into an arrow between tuples. The first elements in the tuples represent the portion of the input and output that is altered, while the second elements are a third type u describing an unaltered portion that bypasses the computation.

first (A s t) -> A (s,u) (t,u)

(Scalaz also defines second as a complementary function to first.
second (A s t) -> A (u, s) (u, t)). Please note that there is no need whatsoever to restrict type of “unaltered portion”. This is to make first and second operators fit into any computation, regardless of its result type. Hence the introduction of the third, independent, type parameter.

A composition operator >>> that can attach a second arrow to a first as long as the first function’s output and the second’s input have matching types

A s t >>> A t u -> A s u

A merging operator *** that can take two arrows, possibly with different input and output types, and fuse them into one arrow between two compound types.

A s t *** A u v -> A (s,u) (t,v)

Wikipedia does not mention it but there is another commonly used combinator called split (&&&). It sends the input to both argument arrows and combines their output.

A s t &&& A s u -> A s (t, u).

I find it really helpful to visualize arrow combinators:

Looking closely at the definitions we are able to coin arrow interface in form of a trait.

Code

I followed Scalaz convention closely here: an id method is added that returns identity arrow (it will come handy later on) and compose is reversed to resemble function composition (we’ll be calling it <<<, instead of >>>).
As you probably noticed from the diagram merge can be implemented as a composition of first and second. Further conclusion that can be drawn from this is that f &&& g = arr(x -> (x, x)) >>> (f *** g).
You might be curious about the naming of Arrow type parameter. It is called =>: to mimic function type’s =>. It reflects that arrow is a generalization of function and enhances function-like types, that is, anything that takes input and produces output. It builds on a less-known Scala feature that let’s you write higher-order type constructor in infix form eg. =>[A, B] is A => B.
Next, we’d like to enhance arrow-like classes with fancy symbolic arrow combinators we all love :-) Following Scalaz convention, we’ll wrap these in the ArrowOps class and provide appropriate implicit conversions.

All this machinery gives us ability to define arrow-like types. One obvious choice is an ordinary Function1.

Function is an arrow

Mapping between functions and arrows is straightforward:
– identity arrow is identity function
– compose is function composition
– first is a function that operates on a 2-tuple argument, mapping first part and leaving 2nd unaltered

Code

I chose to replace merge with something more tailored to functions (and also slightly faster) but we could live with the default one.

Rewrite code using arrows

Now that we have extended functions with arrow combinators, we can use them in our service to make it composable. Let’s sketch business logic flow to analyze how it can be done:

Looks good. Translating this flow back to code gives us very generic function that can be used to implement all the buisness logic we have:

Code

We can customize its behavior by plugging in various functions. For example:

Starting production seems to be a little harder because of multiple arguments involved. But when you think about it, each function with multiple arguments can be changed to a Function1 using case class encapsulation:

It is much easier to add new functionality now. Because the business logic is abstracted out to a flow, the only place that needs to be changed is the flow itself. Let’s review our goal: production lot cannot be modified if its status has been set to done. It’s trivial to introduce it now, we have already seen it in the previous diagram.

Although we have improved internals of existing code a bit there is still much bigger problem to tackle on the outside: to eliminate exceptions.

Even Yoda recommends not to use exception handling for control flow. “Do or do not, there is no try”

Replacing exceptions with Either

Representing various outcomes of a computation with Either forms a powerful pattern. It makes error handling the part of normal control flow and allows for a fully type-safe and functional code in the presence of errors.
Let’s revisit all the places in our code base where exception may be thrown and rewrite them using Either. We’ll represent error cases as subtypes of the new Error class which encode what went wrong in the type and carry some additional information.

Code

But we immediately notice a problem — our shiny arrow stops compiling! If you tried to fix it, it’d become clear that there is no easy way to compose these functions! Every function would have to unpack a value from Eitherand pack result back into a new instance of Either. Resulting code would be horrible mess with a lot of boilerplate. Things look bleak. Seems we’re in worse shape than before…
Fear not. As we said arrows are a general interface to computation. This implies that many different computation types can be expressed using arrows. Do not forget that arrow does not impose restrictions on underlying type as long you can come up with implementations of abstract operations that arrow typeclass needs ie. first/secondand compose. While ordinary A => B functions are clearly not sufficient to express our new idea, there exists another abstraction designed to do that. It is called Kleisli to honor Swiss mathematician who studied properties of categories associated to monads. Going back to our Scala domain Kleisli represents monadiccomputations i.e. functions of type A => M[B]. We’ll be able to implement arrow on Kleisli, creating so called Kleisli arrows ie. arrows that can compose functions of type A => M[B] as long as M is a monad.

What’s a monad?

Monad is bread and butter of functional programming. I’m not going to explain the concept in this blog post. It’d probably take quite a few (posts — pun intended) to just skim through theory and practice of monads. For our purposes it suffices to know that monad is a container with two operations: bind and return (sometimes called unit but we’ll be calling it point to keep things faimilar for Scalaz people). These operations have the following semantics (from wiki):

The return operation takes a value from a plain type and puts it into a monadic container using the constructor, creating a monadic value.
The bind operation takes as its arguments a monadic value and a function from a plain type to a monadic value, and returns a new monadic value.

Many types you’ve probably used thousands of times can be treated as monads. For instance, a famous example of a Monad is List with return creating one element List and bind being Scala’s flatMap. More involved examples include Slick’s Query where return is a Query#apply and bind chains queries together (again, flatMap).
We’ll also put to use the fact that monad is a kind of functor i.e. it can be mapped over (like a list or a map). So we’ll add another operation to monad interface, called fmap that will give us ability to map over monadic values.
Putting this together, we’ll be representing monads as members of the following typeclass:

Code

Because we’ll be using bind quite a lot let’s make it a symbolic operator. I’ve chosen >>= to adhere to a Haskell tradition.

Is Either a monad?

Well, no it is not. But we won’t let that stop us :-)
First of all, monad is of kind * -> * while Either‘s kind is * -> * -> * (that’s fancy way of saying that Monad type constructor takes one type parameter while Either takes two). Then, you cannot compose Either without knowing whether it is Right or Left. Sometimes people say that Either lacks bias e.g. had it been right biased it would have been composable just like Option is by sticking to the RightProjection and bailing out on LeftProjection.
But we can easily form it into Monad ourselves. We just have to use one of the most loathed Scala features called type lambdas to curry Either type constructor into * -> *. Later on I’m going to show how to make syntax easier on the eyes but for now let’s stick to standard ways:

Code

In this code we fixed bias and type kind in one go. (Sorry for the Greek letters, I have some weakness for them :-) ). In case you didn’t come across type lambdas syntax before, { type λ[β] = Either[L, β] })#λ means: produce a new (anonymous) type with one hole but equivalent to Either[L, β] where L has been fixed. We’ll be using type lambdas quite a lot throughout this series, so please make sure that you understand this strange syntax. Implementation-wise we bind and map only with right projection thus giving Either right bias we so much needed.

Implement Kleisli and Kleisli arrow

Kleisli type as such is just a wrapper over functions of type A => M[B]. Still, we can put a few operations into it, provided that M[_] is an instance of monad eg. andThen and compose variants that we’ll reuse for arrow composition and map function that we’ll use later.

Code

To get back an ordinary function from Kleisli without much hassle I have added an implicit conversion from Kleisli to function type.
The most important building block of Kleisli composition is this piece of code
Kleisli((a: A) => this(a) >>= k.run). It gives a recipe of monadic composition: get a monad instance and use this monad’s bind with a function that takes value out of monad and produces new monad. Monad takes care of plumbing. If you look closer that’s exactly what we missed when we tried to use Either with arrows – now instead of implementing it by hand and cluttering our code we extracted this boilerplate into monads and arrows. What is left to be done is to implement Arrow made with Kleislis. That’s easy enough:

Code

Let’s explain a few details. Once again we needed to use type lambdas to trick Scala into thinking that Kleisli is a right type parameter to Arrow trait. We abstracted out monad leaving only arrow’s input and output. All the methods rely on point to create a new monad instance and bind to push a value out of a monad into another one. Thus, you can’t have Kleisli arrow without Monad, these two need to go together. To implement compose we just used andThen syntax from Kleisli. We also have to tell the compiler how to convert our new arrow to ArrowOps to use convenient syntax:

This looks terrible, but well, what can we do. Previous definition was not adequate because it insisted on type of F being of * -> * ->* while Kleisli has got (* -> *) -> * -> * -> * kind.
Now we are finally able to incorporate error handling into our flow

Implement error handling using Kleisli arrows

Let’s go back to the drawing board. The flow can be much simplified because we won’t be relying on side effects to propagate errors. What’s more, handling of errors will be responsibility of an Either monad, so we do not have to write any code or alter the logic to take care of this. Thus, we can enjoy smooth linear flow. A railway, if you will. Hence the term railway oriented programming, coined by Scott Wlashin.

Red lines represent ‘error handling track’. Their presence is caused by how we implemented bind in the Eithermonad i.e. binding is right biased. When Left value is encountered, it breaks the flow. Bold blue lines represent Kleisli composition, they combine monadic values together by unpacking them and feeding the next computation. One problem you might have noticed is the copying function represented by the dotted rectangle. It is not monadic and as such cannot participate in the normal flow.

Integrating non-monadic functions

When composing monadic functions we obtain a monad instance M[B] from M[A] by means of A => M[B], a binding function. Non-monadic functions, on the other hand, are of form A => B. That’s precisely the difference between flatMap and map, and that’s the very reason we implemented map function on Kleisli. Mapping lets us obtain a new monad instance by means of a function that does not have to do anything with monads. To recap – if you have a need to integrate non-monaidc functions into a pipeline, use map.

Back to the code. Now, our business logic can handle errors and normal flow with ease:

Code

We can cross out another requirement: exceptions are gone.
On the other hand we came across some difficulties. First of all, passing the environment had been quite a hassle. Environment represented additional data that logic needed to operate on, and it didn’t adhere to our monadic model. That forced us to rewrite the code a bit, leveraging the fact that what we’ve got after all is functions, and functions can be partially applied and curried. That’s how we were able to completely eliminate env parameter from the equation.
Second, you need type alias to use functions returning Either as Kleisli

no type parameters for method apply: (run: A => M[B])org.virtuslab.blog.kleisli.Kleisli[M,A,B] exist so that it can be applied to arguments (org.virtuslab.blog.kleisli.ProductionLot =>
Either[org.virtuslab.blog.kleisli.Error,org.virtuslab.blog.kleisli.ProductionLot])
[error] — because — 
[error] argument expression’s type is not compatible with formal parameter type;
[error] found : org.virtuslab.blog.kleisli.ProductionLot =>
Either[org.virtuslab.blog.kleisli.Error,org.virtuslab.blog.kleisli.ProductionLot]
[error] required: ?A => ?M[?B]
[error] Kleisli { verify(_, env) } >>>

You may be tempted to employ type lambdas to get rid of alias e.g.

but, aside readability woes, it is path to nowhere because of one of the most famous Scala compiler bugs: SI-2712. Compiler complains that:

value >>> is not a member of
org.virtuslab.blog.kleisli.Kleisli[[R]scala.util.Either[org.virtuslab.blog.kleisli.Error,R],Long,org.virtuslab.blog. kleisli.ProductionLot]

which is because of:

ToArrowOpsFromKleisliLike is not a valid implicit value for (=>
org.virtuslab.blog.kleisli.Kleisli[[R]scala.util.Either[org.virtuslab.blog.kleisli.Error,R],Long,org.virtuslab.blog. kleisli.ProductionLot]) => ?{def >>>: ?} because:
[info] no type parameters for method ToArrowOpsFromKleisliLike: (v: F[G,A,B])(implicit arr: org.virtuslab.blog. kleisli.Arrow[[β, γ]F[G,β,γ]])org.virtuslab.blog.kleisli.ArrowOps[[β, γ]F[G,β,γ],A,B] exist so that it can be applied to arguments
(org.virtuslab.blog.kleisli.Kleisli[[R]scala.util.Either[org.virtuslab.blog.kleisli.Error,R],Long,org.virtuslab.blog. kleisli.ProductionLot])
[info] — because — 
[info] argument expression’s type is not compatible with formal parameter type;
[info] found :
org.virtuslab.blog.kleisli.Kleisli[[R]scala.util.Either[org.virtuslab.blog.kleisli.Error,R],Long,org.virtuslab.blog. kleisli.ProductionLot]
[info] required: ?F[?G, ?A, ?B]

You might utter a cry of disbelief when you see that. After all, it is quite obvious that the following unification makes formal and actual types fit together: {F[_, _, _] / Kleisli, G[_] / [R]scala.util.Either[org.virtuslab.blog.kleisli.Error,R], A / Long, B/ ProductionLot }. Well, your intuition is right, but compiler cannot perform partial polymorphic type inference. Quoting Paul Philips:

Type lambdas are cool and all, but not a single line of the compiler was ever written with them in mind. They’re just not going to work right: the relevant code is not robust.

If you think you can outsmart it introducing exact implicit conversion, compiler will retaliate with not finding implicit arrow instance needed for the conversion.
Instead of tilting with windmills it’s better to refactor it slightly to guide type inference:

Code

Summary

In this part we’ve been able to achieve quite a lot. Starting from uncomposable, imperative code with side effects, we’ve slowly paved our way to a proper functional
code with error handling. It’s as if we’ve built ourselves a little language to help us express various aspects of control flow normally implemented in imperative manner, without compromising on composability. In the next part we’ll extend this example by implementing more requirements that you’d often find in coding business logic eg. logging (side-effects). I’ll also eliminate ugly looking type lambdas. Further down the road we’ll look at the envparam once again and devise a way to handle it more cleanly, thus giving birth to arrow transformers. Stay tuned.