Я ☞ Articles ☞ Bind and traverse with Kleisli morphisms

Previously: Using Yoneda lemma for flipping notation

Flat and Kleisli morphisms

Kleisli is a regular morphism with some Functor in target object:

Previously we covered only flat morpisms. You can see the difference now - Kleisli morphism lifts an object into some functor T. Wait a minute… We already met a diagram with mapping objects and morphisms involving functors already!

So, the question is: what if we use Kleisli morphism instead of flat one? Keep in mind, a lawful Functor should map morphism without affecting objects in any way.

I guess you already see a problem here. Whenever we map this Kleisli source category, we just stack functors one atop another… We should find a way to sort out this mess:

map[+]: from a (tt o) `AR_` into (t a) (t (tt o))

Binding is mapping and joining

One solution is to join these functors into one. But how would we know how to do that? The answer is comes down to searching for a matching natural transformation!

So, if we just compose a mapping of source Kleisli morphism to a flat one and a component of a matching natural transformation we can solve the problem:

map[+] `ho` η[o]: from a (tt o) `AR_` into (t a) (t o)

As a result, Kleisli morphism resides only in source category, but completely eliminated in target category:

For those who already knows what Monad is, you could already recognize a component called join which squash the same functor:

join: t (t i) `AR_` t

However, a notion of Monad is not used in Я. Most of the time you could have two natural transformation that could form a Monad - but there is no use for it for now.

We already saw a covariant functor mapping operator before (yo):

`yo`: t a `AR_` into (from a o) (t o)

So, to make this operator work with a source Kleisli morphism we need to add k letter so a small hook will appear (yok):

`yok`: t a `AR_` into (from a tt o) (t o)

Actually, tt functor should be labeled here, we will cover it a bit later.

Traversal is mapping and swapping

Here is the idea - we will try to use exactly the same Kleisli morphism but instead of joining it in target category we will swap functors!

I bet if you get used to Haskell for some time you already recognized this - it looks like Traversable functor:

map[+] `ho` η[o]: from a (tt o) `AR_` into (t a) (tt (t o))

In this case, we don’t squash wrapped functors and as a result we have Kleisli morphism both on source and target sides:

So, we have small hook on source side - k and big hook on target side - l (yokl):

`yokl`: t a `AR_` into (from a (tt o)) (tt (t o))

Context-free computations?

Kleisli morphisms are great! Just having them you are able to express the most of control flow.

However, they are too powerful for some kind of tasks. Consider such an example: we have two optional values and we want to combine it into one:

?: Optional i `LM` Optional i `AR___` Optional (i `LM` i)

Having Kleisli you can solve it this way (x, y: Optional i):

x `yok` Try `ha` (\x' -> y `yok` Try `ha` (\y' -> x' `lu` y' `yi` Some))

Looks ugly and inneficient! The problem is that using Kleisli involve dependencies. What we want is kind of context-free computations.

There is a way to express it using Monoidal functors.

x `lu'yp` y

We will talk about it next time.

Continue: Context-free computations with Monoidal functors

In case if you want to go deeper into this topic:

• Kleisli Categories