Kleisli category

Let \(\mathbf{C}\) be a category, \(M\) be an Endofunctor and \(\left<M, \mu, \eta\right>\) is a Monad. Then we can construct a new category \(\mathbf{C_M}\) as follows: \[\begin{aligned} \mathrm{ob}(\mathbf{C_M}) = \mathrm{ob}(\mathbf{C}), \nonumber \\ \mathrm{hom}_{\mathbf{C_M}}\left(a, b\right) = \mathrm{hom}_{\mathbf{C}}\left(a, M(b)\right) \nonumber \end{aligned}\] i.e. objects of categories \(\mathbf{C}\) and \(\mathbf{C_M}\) are the same but morphisms from \(\mathbf{C_M}\) form a subset of morphisms \(\mathbf{C}\): \(\mathrm{hom}(\mathbf{C_M}) \subset \mathrm{hom}(\mathbf{C})\). The category is called Kleisli category.

The identity morphism in the Kleisli category is the Natural transformation component \(\eta_a: a \to M(a)\) (Monad) defined by the monad \(\left<M, \mu, \eta\right>\): \[\mathbf{1}_{a \to a}^{C_M} = \eta_a.\] If \(f_M: a \to b\) and \(g_M: b \to c\) are represented in \(\mathbf{C}\) by \(f: a \to M(b)\) and \(g: b \to M(c)\), then their composition in \(\mathbf{C_M}\) is represented by \[\mu_c \circ M(g) \circ f: a \to M(c).\]

Kleisli category has non-trivial composition rules. If we have 2 Morphisms from \(\mathrm{hom}(\mathbf{C_M})\): \[f_M: a \to b\] and \[g_M: b \to c.\] The morphisms have correspondent ones in \(\mathbf{C}\): \[f: a \to M(b)\] and \[g: b \to M(c).\] The composition \(g_M \circ f_M\) gives a new morphism \[h_M = g_M \circ f_M: a \to c.\] The corresponding one from \(\mathbf{C}\) is \[h = \mu_c \circ M(g) \circ f: a \to M(c).\] It has to be pointed out that the compositions in \(\mathbf{C}\) and \(\mathbf{C_M}\) are not the same: \[g_M \circ f_M \ne g \circ f.\]

Kleisli category is widely spread in programming, especially it provides good description for different types of computations, for instance (Moggi 1991; Milewski 2018):

  • Partiality i.e. when a function is not defined for each input, for instance the following expression is undefined (or partially defined) for \(x = 0\): \(f(x) = \frac{1}{x}\)

  • Non-Determinism i.e. when multiple outputs are possible

  • Side-effects i.e. when a function communicates with an environment

  • Exception i.e. when some input is incorrect and can produce an abnormal result. Therefore it is the same as Partiality and will be considered below as the same type of computation.

  • Continuation i.e. when we need to save the current state of the computation and be able to restore it on demand later

  • Interactive input i.e. a function that reads data from an input device (keyboard, mouse, etc.)

  • Interactive output i.e. a function that writes data to an output device (monitor etc.)

Partiality and Exception

Partial functions and exceptions can be processed via a monad called Maybe. There will be implementations in different languages below. And the usage example for the following function implementation \[h(x) = \frac{1}{2 \sqrt{x}}.\] The function is a composition of 3 functions: \[\begin{aligned} f_1(x) = \sqrt{x}, \nonumber \\ f_2(x) = 2 \cdot x, \nonumber \\ f_3(x) = \frac{1}{x} \end{aligned}\] and as a result the goal can be implemented as the following composition: \[h = f_3 \circ f_2 \circ f_1.\] \(f_2\) is a Pure function and is defined \(\forall x \in \mathbb{R}\). The functions \(f_1, f_3\) are partially defined.

Haskell example

The Maybe monad can be implemented as follows

  instance Monad Maybe where
    return = Just
    join Just( Just x) = Just x
    join _ = Nothing

Our functions (Partiality and Exception) can be implemented as follows

f1 :: (Ord a, Floating a) => a -> Maybe a
f1 x = if x >= 0 then Just(sqrt x) else Nothing 

f2 :: Num a => a -> Maybe a
f2 x = Just (2*x)

f3 :: (Eq a, Fractional a) => a -> Maybe a
f3 x = if x /= 0 then Just(1/x) else Nothing

The \(h\) (Partiality and Exception) is the composition via bind operator:

h :: (Ord a, Floating a) => a -> Maybe a
h x = (return x) >>= f1 >>= f2 >>= f3

The usage example is the following:

*Main> h 4
Just 0.25
*Main> h 1
Just 0.5
*Main> h 0
Nothing
*Main> h (-1)
Nothing

C++ example

The Maybe monad can be implemented as follows

template <class A> using Maybe = std::optional<A>;

template < class A, class B> 
Maybe<B> fmap(std::function<B(A)> f, Maybe<A> a) {
  if (a) {
    return f(a.value());
  }
  return {};
}

template < class A> 
Maybe<A> pure(A a) {
  return a;
}

template < class A> 
Maybe<A> join(Maybe< Maybe<A> > a){
  if (a) {
    return a.value();
  }
  return {};
}

Our functions (Partiality and Exception) can be implemented as follows

std::function<Maybe<float>(float)> f1 =
    [](float x) {
      if (x >= 0) {
        return Maybe<float>(sqrt(x));
      }
      return Maybe<float>();
    };

std::function<Maybe<float>(float)> f2 = [](float x) { return 2 * x; };

std::function<Maybe<float>(float)> f3 =
    [](float x) {
      if (x != 0) {
        return Maybe<float>(1 / x);
      }
      return Maybe<float>();
    };
}

The \(h\) (Partiality and Exception) is the composition via bind operator:

auto h(float x) {
  Maybe<float> a = pure(x);
  return bind(f3,bind(f2,bind(f1, a)));
};

Non-Determinism

The situation when a function returns several values is not applicable for Set category but can appear for Rel category. From other hand the non standard situation is required for practical applications and as result has to be modeled in programming languages. The List monad is used for it.

Haskell example

  instance Monad [] where
    return x = [x]
    join = concat

Side effects and interactive input/output

TBD

Continuation

TBD

Milewski, B. 2018. Category Theory for Programmers. Bartosz Milewski. https://github.com/hmemcpy/milewski-ctfp-pdf/releases/download/v0.7.0/category-theory-for-programmers.pdf.
Moggi, Eugenio. 1991. “Notions of Computation and Monads.” Inf. Comput. 93 (1): 55–92. http://fsl.cs.illinois.edu/pubs/moggi-1991-ic.pdf.