Kleisli

Kleisli is a data type that will come in handy often, especially if you are working with monadic functions. Monadic functions are functions that return a monadic value - for instance, a function may return an Option[Int] or an Xor[String, List[Double]].

How then do we compose these functions together nicely? We cannot use the usual compose or andThen methods without having functions take an Option or Xor as a parameter, which can be strange and unwieldy.

We may also have several functions which depend on some environment and want a nice way to compose these functions to ensure they all receive the same environment. Or perhaps we have functions which depend on their own "local" configuration and all the configurations together make up a "global" application configuration. How do we have these functions play nice with each other despite each only knowing about their own local requirements?

These situations are where Kleisli is immensely helpful.

Functions

One of the most useful properties of functions is that they compose. That is, given a function A => B and a function B => C, we can combine them to create a new function A => C. It is through this compositional property that we are able to write many small functions and compose them together to create a larger one that suits our needs.

scala> val twice: Int => Int =
     |   x => x * 2
twice: Int => Int = <function1>

scala> val countCats: Int => String =
     |   x => if (x == 1) "1 cat" else s"$x cats"
countCats: Int => String = <function1>

scala> val twiceAsManyCats: Int => String =
     |   twice andThen countCats
twiceAsManyCats: Int => String = <function1>

scala>   // equivalent to: countCats compose twice
     | 
     | twiceAsManyCats(1) // "2 cats"
res2: String = 2 cats

Sometimes, our functions will need to return monadic values. For instance, consider the following set of functions.

scala> val parse: String => Option[Int] =
     |   s => if (s.matches("-?[0-9]+")) Some(s.toInt) else None
parse: String => Option[Int] = <function1>

scala> val reciprocal: Int => Option[Double] =
     |   i => if (i != 0) Some(1.0 / i) else None
reciprocal: Int => Option[Double] = <function1>

As it stands we cannot use Function1.compose (or Function1.andThen) to compose these two functions. The output type of parse is Option[Int] whereas the input type of reciprocal is Int.

This is where Kleisli comes into play.

Kleisli

At it's core, Kleisli[F[_], A, B] is just a wrapper around the function A => F[B]. Depending on the properties of the F[_], we can do different things with Kleislis. For instance, if F[_] has a FlatMap[F] instance (we can call flatMap on F[A] values), we can compose two Kleislis much like we can two functions.

scala> import cats.FlatMap
import cats.FlatMap

scala> import cats.syntax.flatMap._
import cats.syntax.flatMap._

scala> final case class Kleisli[F[_], A, B](run: A => F[B]) {
     |   def compose[Z](k: Kleisli[F, Z, A])(implicit F: FlatMap[F]): Kleisli[F, Z, B] =
     |     Kleisli[F, Z, B](z => k.run(z).flatMap(run))
     | }
defined class Kleisli

Returning to our earlier example:

scala> // Bring in cats.FlatMap[Option] instance
     | import cats.std.option._
import cats.std.option._

scala> val parse = Kleisli((s: String) => try { Some(s.toInt) } catch { case _: NumberFormatException => None })
parse: Kleisli[Option,String,Int] = Kleisli(<function1>)

scala> val reciprocal = Kleisli((i: Int) => if (i == 0) None else Some(1.0 / i))
reciprocal: Kleisli[Option,Int,Double] = Kleisli(<function1>)

scala> val parseAndReciprocal = reciprocal.compose(parse)
parseAndReciprocal: Kleisli[Option,String,Double] = Kleisli(<function1>)

Kleisli#andThen can be defined similarly.

It is important to note that the F[_] having a FlatMap (or a Monad) instance is not a hard requirement - we can do useful things with weaker requirements. Such an example would be Kleisli#map, which only requires that F[_] have a Functor instance (e.g. is equipped with map: F[A] => (A => B) => F[B]).

scala> import cats.Functor
import cats.Functor

scala> final case class Kleisli[F[_], A, B](run: A => F[B]) {
     |   def map[C](f: B => C)(implicit F: Functor[F]): Kleisli[F, A, C] =
     |     Kleisli[F, A, C](a => F.map(run(a))(f))
     | }
defined class Kleisli

Below are some more methods on Kleisli that can be used so long as the constraint on F[_] is satisfied.

Method | Constraint on F[_] --------- | ------------------- andThen | FlatMap compose | FlatMap flatMap | FlatMap lower | Monad map | Functor traverse | Applicative

Type class instances

The type class instances for Kleisli, like that for functions, often fix the input type (and the F[_]) and leave the output type free. What type class instances it has tends to depend on what instances the F[_] has. For instance, Kleisli[F, A, B] has a Functor instance so long as the chosen F[_] does. It has a Monad instance so long as the chosen F[_] does. The instances in Cats are laid out in a way such that implicit resolution will pick up the most specific instance it can (depending on the F[_]).

An example of a Monad instance for Kleisli would be:

scala> import cats.syntax.flatMap._
import cats.syntax.flatMap._

scala> import cats.syntax.functor._
import cats.syntax.functor._

scala> // Alternatively we can import cats.implicits._ to bring in all the
     | // syntax at once (as well as all type class instances)
     | 
     | // We can define a FlatMap instance for Kleisli if the F[_] we chose has a FlatMap instance
     | // Note the input type and F are fixed, with the output type left free
     | implicit def kleisliFlatMap[F[_], Z](implicit F: FlatMap[F]): FlatMap[Kleisli[F, Z, ?]] =
     |   new FlatMap[Kleisli[F, Z, ?]] {
     |     def flatMap[A, B](fa: Kleisli[F, Z, A])(f: A => Kleisli[F, Z, B]): Kleisli[F, Z, B] =
     |       Kleisli(z => fa.run(z).flatMap(a => f(a).run(z)))
     | 
     |     def map[A, B](fa: Kleisli[F, Z, A])(f: A => B): Kleisli[F, Z, B] =
     |       Kleisli(z => fa.run(z).map(f))
     |   }
kleisliFlatMap: [F[_], Z](implicit F: cats.FlatMap[F])cats.FlatMap[[γ]Kleisli[F,Z,γ]]

Below is a table of some of the type class instances Kleisli can have depending on what instances F[_] has.

Type class | Constraint on F[_] -------------- | ------------------- Functor | Functor Apply | Apply Applicative | Applicative FlatMap | FlatMap Monad | Monad Arrow | Monad Split | FlatMap Strong | Functor SemigroupK* | FlatMap MonoidK* | Monad

*These instances only exist for Kleisli arrows with identical input and output types; that is, Kleisli[F, A, A] for some type A. These instances use Kleisli composition as the combine operation, and Monad.pure as the empty value.

Also, there is an instance of Monoid[Kleisli[F, A, B]] if there is an instance of Monoid[F[B]]. Monoid.combine here creates a new Kleisli arrow which takes an A value and feeds it into each of the combined Kleisli arrows, which together return two F[B] values. Then, they are combined into one using the Monoid[F[B]] instance.

Other uses

Monad Transformers

Many data types have a monad transformer equivalent that allows us to compose the Monad instance of the data type with any other Monad instance. For instance, OptionT[F[_], A] allows us to compose the monadic properties of Option with any other F[_], such as a List. This allows us to work with nested contexts/effects in a nice way (for example, in for-comprehensions).

Kleisli can be viewed as the monad transformer for functions. Recall that at its essence, Kleisli[F, A, B] is just a function A => F[B], with niceties to make working with the value we actually care about, the B, easy. Kleisli allows us to take the effects of functions and have them play nice with the effects of any other F[_].

This may raise the question, what exactly is the "effect" of a function?

Well, if we take a look at any function, we can see it takes some input and produces some output with it, without having touched the input (assuming the function is pure, i.e. referentially transparent). That is, we take a read-only value, and produce some value with it. For this reason, the type class instances for functions often refer to the function as a Reader. For instance, it is common to hear about the Reader monad. In the same spirit, Cats defines a Reader type alias along the lines of:

scala> // We want A => B, but Kleisli provides A => F[B]. To make the types/shapes match,
     | // we need an F[_] such that providing it a type A is equivalent to A
     | // This can be thought of as the type-level equivalent of the identity function
     | type Id[A] = A
defined type alias Id

scala> type Reader[A, B] = Kleisli[Id, A, B]
defined type alias Reader

scala> object Reader {
     |   // Lifts a plain function A => B into a Kleisli, giving us access
     |   // to all the useful methods and type class instances
     |   def apply[A, B](f: A => B): Reader[A, B] = Kleisli[Id, A, B](f)
     | }
defined object Reader

scala> type ReaderT[F[_], A, B] = Kleisli[F, A, B]
defined type alias ReaderT

scala> val ReaderT = Kleisli
ReaderT: Kleisli.type = Kleisli

The ReaderT value alias exists to allow users to use the Kleisli companion object as if it were ReaderT, if they were so inclined.

The topic of functions as a read-only environment brings us to our next common use case of Kleisli - configuration.

Configuration

Functional programming advocates the creation of programs and modules by composing smaller, simpler modules. This philosophy intentionally mirrors that of function composition - write many small functions, and compose them to build larger ones. After all, our programs are just functions.

Let's look at some example modules, where each module has it's own configuration that is validated by a function. If the configuration is good, we return a Some of the module, otherwise a None. This example uses Option for simplicity - if you want to provide error messages or other failure context, consider using Xor instead.

scala> case class DbConfig(url: String, user: String, pass: String)
defined class DbConfig

scala> trait Db
defined trait Db

scala> object Db {
     |   val fromDbConfig: Kleisli[Option, DbConfig, Db] = ???
     | }
defined object Db
warning: previously defined trait Db is not a companion to object Db.
Companions must be defined together; you may wish to use :paste mode for this.

scala> case class ServiceConfig(addr: String, port: Int)
defined class ServiceConfig

scala> trait Service
defined trait Service

scala> object Service {
     |   val fromServiceConfig: Kleisli[Option, ServiceConfig, Service] = ???
     | }
defined object Service
warning: previously defined trait Service is not a companion to object Service.
Companions must be defined together; you may wish to use :paste mode for this.

We have two independent modules, a Db (allowing access to a database) and a Service (supporting an API to provide data over the web). Both depend on their own configuration parameters. Neither know or care about the other, as it should be. However our application needs both of these modules to work. It is plausible we then have a more global application configuration.

scala> case class AppConfig(dbConfig: DbConfig, serviceConfig: ServiceConfig)
defined class AppConfig

scala> class App(db: Db, service: Service)
defined class App

As it stands, we cannot use both Kleisli validation functions together nicely - one takes a DbConfig, the other a ServiceConfig. That means the FlatMap (and by extension, the Monad) instances differ (recall the input type is fixed in the type class instances). However, there is a nice function on Kleisli called local.

scala> final case class Kleisli[F[_], A, B](run: A => F[B]) {
     |   def local[AA](f: AA => A): Kleisli[F, AA, B] = Kleisli(f.andThen(run))
     | }
defined class Kleisli

What local allows us to do is essentially "expand" our input type to a more "general" one. In our case, we can take a Kleisli that expects a DbConfig or ServiceConfig and turn it into one that expects an AppConfig, so long as we tell it how to go from an AppConfig to the other configs.

Now we can create our application config validator!

scala> final case class Kleisli[F[_], Z, A](run: Z => F[A]) {
     |   def flatMap[B](f: A => Kleisli[F, Z, B])(implicit F: FlatMap[F]): Kleisli[F, Z, B] =
     |     Kleisli(z => F.flatMap(run(z))(a => f(a).run(z)))
     | 
     |   def map[B](f: A => B)(implicit F: Functor[F]): Kleisli[F, Z, B] =
     |     Kleisli(z => F.map(run(z))(f))
     | 
     |   def local[ZZ](f: ZZ => Z): Kleisli[F, ZZ, A] = Kleisli(f.andThen(run))
     | }
defined class Kleisli

scala> case class DbConfig(url: String, user: String, pass: String)
defined class DbConfig

scala> trait Db
defined trait Db
warning: previously defined object Db is not a companion to trait Db.
Companions must be defined together; you may wish to use :paste mode for this.

scala> object Db {
     |   val fromDbConfig: Kleisli[Option, DbConfig, Db] = ???
     | }
defined object Db
warning: previously defined trait Db is not a companion to object Db.
Companions must be defined together; you may wish to use :paste mode for this.

scala> case class ServiceConfig(addr: String, port: Int)
defined class ServiceConfig

scala> trait Service
defined trait Service
warning: previously defined object Service is not a companion to trait Service.
Companions must be defined together; you may wish to use :paste mode for this.

scala> object Service {
     |   val fromServiceConfig: Kleisli[Option, ServiceConfig, Service] = ???
     | }
defined object Service
warning: previously defined trait Service is not a companion to object Service.
Companions must be defined together; you may wish to use :paste mode for this.

scala> case class AppConfig(dbConfig: DbConfig, serviceConfig: ServiceConfig)
defined class AppConfig

scala> class App(db: Db, service: Service)
defined class App

scala> def appFromAppConfig: Kleisli[Option, AppConfig, App] =
     |   for {
     |     db <- Db.fromDbConfig.local[AppConfig](_.dbConfig)
     |     sv <- Service.fromServiceConfig.local[AppConfig](_.serviceConfig)
     |   } yield new App(db, sv)
appFromAppConfig: Kleisli[Option,AppConfig,App]

What if we need a module that doesn't need any config validation, say a strategy to log events? We would have such a module be instantiated from a config directly, without an Option - we would have something like Kleisli[Id, LogConfig, Log] (alternatively, Reader[LogConfig, Log]). However, this won't play nice with our other Kleislis since those use Option instead of Id.

We can define a lift method on Kleisli (available already on Kleisli in Cats) that takes a type parameter G[_] such that G has an Applicative instance and lifts a Kleisli value such that its output type is G[F[B]]. This allows us to then lift a Reader[A, B] into a Kleisli[G, A, B]. Note that lifting a Reader[A, B] into some G[_] is equivalent to having a Kleisli[G, A, B] since Reader[A, B] is just a type alias for Kleisli[Id, A, B], and type Id[A] = A so G[Id[A]] is equivalent to G[A].

Source:	Github
Chat:	Gitter
Build:	Travis
Api:	Scaladoc

Cats

Kleisli

Functions

Kleisli

Type class instances

Other uses

Monad Transformers

Configuration

useful links