Kleisli composition by Mark Seemann
A way to compose two monadic functions. An article for object-oriented programmers.
This article is an instalment in an article series about monads.
There's a bit of groundwork which will be useful before we get to the monad laws. There are two ways to present the monad laws. One is quite unintuitive, but uses only the concepts already discussed in the introductory article. The other way to present the laws is much more intuitive, but builds on a derived concept: Kleisli composition.
I find it preferable to take the intuitive route, even if it requires this little detour around the Kleisli category.
Monadic functions #
Imagine some monad - any monad. It could be Maybe (AKA Option), Either (AKA Result), Task, State, etcetera. In Haskell notation we denote it m. (Don't worry if you don't know Haskell. The type notation is fairly intuitive, and I'll explain enough of it along the way.)
You may have a function that takes some input and returns a monadic value. Perhaps it's a parser that takes a string as input and returns a Maybe or Either as output:
String -> Maybe Int
Perhaps it's a database query that takes an ID as input and returns a Task or IO value:
UUID -> IO Reservation
Notice that in Haskell, you write the input to the left of the output. (This is also the case in F#.) Functions looks like arrows that point from the input to the output, which is a common depiction that I've also used before.
If we generalise this notation, we would write a monadic function like this:
a -> m b
a is a generic type that denotes input. It could be String or UUID as shown above, or anything else. Likewise, b is another generic type that could be Int, Reservation, or anything else. And m, as already explained, may be any monad. The corresponding C# method signature would be:
Func<T, Monad<T1>>
In C#, it's idiomatic to name generic type arguments T and T1 rather than a and b, but the idea is the same.
The previous article used Functor<T> as a stand-in for any functor. Likewise, now that you know what a monad is, the type Monad<T> is a similar pretend type. It symbolises 'any monad'.
Kleisli composition #
In Functions as pipes you got a visual illustration of how functions compose. If you have a function that returns a Boolean value, you can use that Boolean value as input to a function that accepts Boolean values as input. Generalised, if one function returns a and another function accepts a as input, you can compose these two functions:
(a -> b) -> (b -> c) -> (a -> c)
A combinator of this type takes two functions as input: a -> b (a function from a to b) and (b -> c), and returns a new function that 'hides' the middle step: a -> c.
If this is possible, it seems intuitive that you can also compose monadic functions:
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
The >=> operator is known as the fish operator - or more precisely the right fish operator, since there's also a left fish operator <=<.
This is known as Kleisli composition. In C# you could write it like this:
public static Func<T, Monad<T2>> Compose<T, T1, T2>( this Func<T, Monad<T1>> action1, Func<T1, Monad<T2>> action2) { return x => action1(x).SelectMany(action2); }
Notice that Kleisli composition works for any monad. You don't need any new abilities in order to compose a monad in this way. The composition exclusively relies on SelectMany (monadic bind).
Here's a usage example:
Func<string, Monad<int>> f = s => Monad.Return(s.Length); Func<int, Monad<bool>> g = i => Monad.Return(i % 2 == 0); Func<string, Monad<bool>> composed = f.Compose(g);
The Compose method corresponds to the right fish operator, but obviously you could define an overload that flips the arguments. That would correspond to the left fish operator.
Universality #
Kleisli composition seems compelling, but in reality I find that I rarely use it. If it isn't that useful, then why dedicate an entire article to it?
As I wrote in the introduction, it's mostly because it gives us an intuitive way to describe the monad laws.
Kleisli arrows form a category. As such, it's a universal abstraction. I admit that this article series has strayed away from its initial vision of discussing category theory, but I still find it assuring when I encounter some bedrock of theory behind a programming concept.
Conclusion #
Kleisli composition lets you compose two (or more) compatible monadic functions into a single monadic function.
Next: Monad laws.
