Introduction to Functional Programming (4/4)

Monads and Category Theory

2023/04/30

In the previous article, we explored how Functors can be used to abstract over different types of containers. In this article, we will delve into Monads, another critical concept in Category Theory and Functional Programming. Monads, like Functors, are about structure and provide a language that simplifies and beautifies programs.

Monads definition in programming languages

There are many equivalent definition in computer science for Monads. One requires concept that should be familiar to most programmers. A Monad M is a type constructor equipped with (written with pseudocode):

As mentionned in my previous post, fmap defines a functor. As a consequence, a monad is a functor equipped with the additional methods flat and unit. In Haskell, this would be defined as follows:

class Functor m => Monad' m where
    flat :: m (m a) -> m a
    unit :: a -> m a

A more typical definition of a Monad is a type constructor equipped with a fmap method and two additional methods (written with pseudocode):

In haskell, it would be defined as:

class Functor => Monad'' m where
    flatmap :: (a -> m b) -> m a -> m b
    unit :: a -> m a

The two definitions of a Monad are equivalent, as we can construct one from the other. Indeed, given a type constructor M equipped with fmap and flat, we can construct a flatmap by defining flatmap f = flat . fmap f which is indeed of type M[A] -> (A -> M[B]) -> M[B]. We can also construct a flat method by applying flatmap to the Id = \x -> x method (which is the trivial identity function).

In addition to implementing the class functions, all instances of Monad should satisfy the following equations, or monad laws:

flatmap k (return a) =  k a -- Left identity:
flatmap return m = m -- Right identity:
flatmap (\x -> flatmap h $ k x) m  =  flatmap h $ flatmap k m --Associativity

Why do we need monads in functional programming languages

With an understanding of what a monad is, we can delve into its significance and applications. The utility of monads in functional programming is paramount, as they enable the resolution of fundamental issues, including non-deterministic functions like random functions, accessing and modifying states through side effects, and managing exceptions when functions fail, among other use cases.

Monads allow you to compose functions which incorporate this type of behavior. Let us look at an example in Python to illustrate the usage of Monads for loggers.

Typically, in imperative programming languages, loggers are implemented using side effects because they modify the state of an external object through a command declared inside a function. In Python, for instance, this behavior can be seen in the following code:

import logging
from typing import *

logger = logging.getLogger(__name__)

def my_cool_func(num: int) -> int:
    logger.info('We begin to compute cool stuff.') # Logger object is modified
    num_out = (num + 1) * 2
    return num_out

Since the global variable logger is changed each time my_cool_func is executed, this function is impure. However, we can transform it into a pure function by making the logger a variable and an output of the function, as shown below:

def my_cool_func(num: int, logger: str) -> Tuple[int, str]:
    new_logger = logger + 'We begin to compute cool stuff.'
    num_out = (num + 1) * 2
    return num_out, new_logger

But if we write two such functions, they would not be easily composable. To make them composable, we can rewrite them to return only the new logs of the function, as follows:

def my_cool_func(num: int) -> Tuple[int, str]:
    logs = 'We begin to compute cool stuff.'
    num_out = (num + 1) * 2
    return num_out, logs

def another_cool_func(num: int) -> Tuple[bool, str]:
    logs = 'Now, things are getting serious'
    if num > 10:
        return True, logs
    else:
        return False, logs

Now, we have two functions of type int -> (int, str) and int -> (bool, str), which can be easily composed using a monad. Specifically, we can use the Writer monad, which can be defined as follows:

T = TypeVar('T')
Writer = Tuple[T, str]

def unit_writer(val: T) -> Writer[T]:
    return Writer(val, '')

def fmap_writer(func: Callable[[T], U], x: Writer[T]) -> Writer[U]:
    return Writer(func(x[0]), x[1])

def flatmap_writer(func: Callable[[T], Writer[U]], x: Writer[T]) -> Writer[U]:
    x_out, logs_out = func(x[0])
    return Writer(x_out, x[1] + logs_out)

With this, we can compose the functions in a concise and type-safe way, as shown below:

x_in = Writer(4, '')
x_out = flatmap_writer(another_cool_func, flatmap_writer(my_cool_func, x_in))

To achieve even greater concision, we can create a method called fish_writer that directly composes functions. This method takes in two functions of type T -> Writer[U] and U -> Writer[V], and returns a new function of type T -> Writer[V].

def fish_writer(func1: Callable[[T], Writer[U]], func2: Callable[[U], Writer[V]]) -> Callable[[T], Writer[V]]:
    def new_func(x: T) -> Writer[V]:
        return flatmap_writer(another_cool_func, flatmap_writer(my_cool_func, x_in))
    return new_func

x_in = Writer(4, '')
final_cool_func = fish_logger(my_cool_func, another_cool_func)
x_out = final_cool_func(x_in)

We can now use the fish_writer operator to compose pure logger functions of type A -> (B, str) and B -> (C, str) into a new function of type A -> (C, str). This is accomplished using the final_cool_func function, which is the result of calling fish_logger on my_cool_func and another_cool_func.

It is remarkable that, despite the need for logging, we can still maintain function purity by leveraging the power of monads to compose functions with enriched values in an elegant and type-safe manner. In fact, monads provide a high degree of control and safety when dealing with side effects. In the following sections, we will explore more examples of this concept using Haskell.

Example of Monads in haskell

In this section, we will demonstrate some common monads using Haskell code.

The List Monad

The List is the most classical functor in Haskell and can be defined as:

instance Monad'([a]) where
    unit x = [x]
    flatmap f (x :: xs) = f x ++ flatmap f xs
    flatmap f [] = []

This example is quite intuitive and serves as a reference for understanding how flatmap and unit work. The unit function constructs a list with one element. Using the flatmap function, we apply the function f to each element of the list (the map step) and concatenate all the results (the flat step).

The Writer monad

We already studied the Writer monad for loggers. Now, let’s rewrite the same example of the Writer monad in Haskell, which was written in Python in the previous section, by generalizing the logger of type string to any monoid type w. In Haskell, a Monoid is a type class that has a neutral element (mempty) and a multiplicative method (mappend), which are defined as:

class Monoid' m where
    mempty :: m
    mappend :: m -> m -> m

The Writer monad can be defined with any monoid type:

newtype Writer w a = Writer (a, w)

instance Functor (Writer w) where
    fmap f (Writer (a, w)) = Writer (f a, w)

instance Monoid' w => Monad'' (Writer w) where
    unit a = Writer (a, mempty)
    flatmap f (Writer (a, w)) = 
        let (Writer (a2, w2)) = f a in Writer (a2, mappend w w2)

We can also easily define the fish operator:

fish :: (a -> Writer w b) -> (b -> Writer w c) -> Writer w a -> Writer w c
fish f1 f2 = flatmap f2 . flatmap f1

The Reader Monad

Let’s explore the Reader Monad and how it can be defined in Haskell. Similar to the Writer monad, a function with read-only access to some external data can be replaced by a function that takes the external data as an additional argument.

The Reader could be defined as (a, e) and a pure function as (a, e) -> b. However, this doesn’t define a monad directly, but a comonad (see the last section for more details). Using currying, we can transform any function of this type into a function of type a -> e -> b which can also be seen as a -> (e -> b), which has a monadic structure. Thus, the Reader can be defined as:

newtype Reader e a = Reader (e -> a)

We can think the Reader as a program that for any environment e, produces the desired output relative to the environment. We can define a function to exectute the Reader:

runReader :: Reader e a -> e -> a
runReader (Reader f) e = f e

This is particularly useful for config files, which can serve as inputs for many functions. Our goal now is to define it as a monad, which will allow us to compose functions of Reader.

instance Monad'(Reader e) where
    unit a = \e -> a
    flatmap f (Reader g) = Reader $ f.g

unit a is defined as the constant function which always return a. flatmap f (Reader g) is defined by composing the wrapped function g and the applied function f. With this, we can now use the Reader to compose functions with read-only access to external data in a pure and elegant way.

Exception/Maybe Monad

A function that throws an exception can be seen as a function that is undefined for some arguments. In the previous article on functional programming, we defined the Maybe functor as Just a or Nothing, which is actually a monad. The Maybe monad can be used to prevent errors by defining functions that return Nothing when the input is invalid and Just a when it’s valid. With its monadic structure, it’s easy to compose functions that return Maybe types. Here is an example of a Monad instance for Maybe:

instance Monad Maybe where
    unit a = Just a 
    flatmap f (Just a) = f a
    flatmap f Nothing = Nothing

If we think about parallel jobs, the Maybe monad can be used to run multiple functions with different inputs and possible errors, and pipe them so that if there is an issue in one process, it returns Nothing without impacting the other processes. This can be very useful in data engineering.

Monads in category theory

In this section, we will quickly study the mathematical definition of a monad. Let $(C, \otimes, 1)$ be a monoidal category. A monoidal category is a category that is equipped with a bifunctor $C \otimes C \rightarrow C$ (also called the tensor product) and an object $I$ that serves as both a left and right identity for $\otimes$.

Note that for any category C, one can form its category of endofunctors End_C. The composition of functors $\circ$ gives $End_C$ the structure of a monoidal category with unit $Id_C$. We denote this monoidal category as $(End_C, \circ, Id)$.

Definition

A Monad $M$ in $C$ is a Monoid in the category of endofunctors $(End_C, \circ, Id)$, i.e., $M$ is an endofunctor $M: C \rightarrow C$ equipped with the natural transformations:

that satisfy the associativity and unit coherence diagrams.

If we go back to our first definition of a monad, for any type $T$, $\eta_T: M\circ M(T) \rightarrow M(T)$ and $unit_T: Id(T) \rightarrow M(T)$ correspond to the flat and unit methods defined in the first section of the article, which needs to verify associativity and unit coherence.

A note on the Kleiski category

An interesting point of view on Monads is the Kleiski category. The Kleiski category associated with the monad $M$ is defined as follows:

Composition is defined as follows:

Given $f: A \rightarrow M(B)$ and $g: B \rightarrow M(C)$, the composition $g \circ f$ is defined as $x \rightarrow flatmap(g, f(x))$. Actually, this composition corresponds to the fish operator defined in the previous section. Note that the kleiski category and the monads are two equivalent framework to define the same concept.

An interesting point is that we can define a functor from the category of Kleiski $C_F$ to the category $C$ (i.e $C_F \rightarrow C$) which maps each type $T$ to the type $M(T)$, and map each morphism $A \rightarrow M(B)$ to a morphism $M(A) \rightarrow M(B)$, which corresponds to the operation of the flatmap method defined in the first section.

Comonads ?

In category theory, the prefix “co” typically means that we reverse the direction of the arrows in the category. In Haskell, we can define comonads as follows:

class Functor m => Comonad' m where
    counit :: m a -> a -- also called extract
    coflat :: m a -> m (m a) -- also called duplicate
    coflatmap :: (m a -> b) -> m a -> m b -- also called extend

As you can see, a comonad is the dual concept of a monad. It has a “counit” operation which extracts the value of a comonadic type, a “coflat” operation which duplicates a comonadic type, and a “coflatmap” operation which composes functions in the opposite direction compared to the “bind” operation in monads. In the context of Kleisli categories, the co-Kleisli categories associated with a comonad $F$ correspond to the category where objects are types, and arrows are morphisms of type $ F(A) \rightarrow B$.

One example of a comonad is the reader comonad, which can be used to represent read-only computations that depend on some environment (such as a configuration file or a database). In the original definition of Kleisli arrows, read-only computations were represented as functions of type $(a, e) \rightarrow b$, which could be transformed into Kleisli arrows of type $a \rightarrow (e \rightarrow b)$. However, notice that the original representation already has the form of co-Kleisli arrows. Hence, $(a, e)$ can be turned into a comonad.

newtype Product e a = Product (a, e)

instance Comonad' (Product e a) where
    counit (Product (a, e)) = a
    coflat (Product (a, e)) = Product (Product (a, e), e)
    coflatmap f (Product (a, e)) = Product (f Product (a, e)) e

The Product comonad, also known as the Reader comonad, is useful for passing the same data (such as a configuration) to multiple functions. Functions of type Product[A] -> B can be composed using the Product comonad.

A last note on the definition of monads in haskell

A last note on the definition of monads in Haskell: it’s important to note that the definition of a monad in Haskell is slightly different from the mathematical definition we discussed earlier, and the definition I gave in the first section. In Haskell, a monad is a type constructor that implements the Monad type class, which provides the functions return and bind (denoted by the infix operator »=) and obeys the three monad laws. However, all the definitions are equivalent, and all lead to the ability of chaining monadic functions. The comonads discussed in the previous section also have their own implementation in Haskell, with the Comonad type class providing functions like extract and extend.

Conclusion

In conclusion, monads in Haskell are a powerful abstraction for handling effects in functional programming. They allow for a clean and modular way to handle side-effects while keeping the purity of the code intact. Monads also provide a compositional structure that makes it easy to combine different effects together. In addition to their importance in functional programming, monads have connections to category theory, which provides a deep and abstract understanding of these concepts. While monads can seem daunting at first, they are an essential tool for any serious Haskell programmer to master. By understanding monads, you can write more expressive and maintainable code, and take your functional programming skills to the next level. I hope you enjoyed this (short) introduction to monads in functional programming. Talk to you soon.