Kleisli category

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

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

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

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

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

C++ example

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 {};
}

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>();
    };

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

The examples above describe computations that can fail. Another common use of the same idea is sequencing computations with side effects. In Haskell an interactive action with result of type a is represented by a value of type IO a. A function of type \[a \to \mathrm{IO}\, b\] can be treated as a morphism in the Kleisli category of the IO monad. Kleisli composition sequences two such actions: the first action is performed, its result is passed to the second action, and the whole expression is again an action.

Thus the categorical structure separates the pure description of sequencing from the concrete effect being modelled. The same composition law is used for partiality, non-determinism, state, exceptions, and interactive input/output; only the monad changes.

Continuation

Continuation passing is another computation pattern that can be expressed by a monad. Fix a result type \(r\). A computation with an intermediate result of type \(a\) can be represented by \[\mathrm{Cont}\ r\ a = (a \to r) \to r.\] Instead of returning an \(a\) directly, such a computation receives the rest of the program, called a continuation, and decides how to call it.

The unit operation sends a value to the computation that immediately passes the value to its continuation. Kleisli composition connects two continuation passing computations by building a new continuation for the first one from the second one. This is useful for describing control flow where the next step of the computation is explicit.