10.4 Kleisli category and free algebras

Kleisli categories and free algebras are key concepts in understanding monads. Kleisli categories represent monadic computations as morphisms, allowing for easy composition. This simplifies working with monads in practical applications.

Free algebras, on the other hand, provide the most general structure for a given monad. They're closely linked to Kleisli categories through adjunctions, offering a different perspective on monadic structures and their properties.

Kleisli Category

Kleisli category for monads

• The Kleisli category $\mathcal{C}_T$ is constructed from a monad $(T, \eta, \mu)$ on a category $\mathcal{C}$
  • Objects in $\mathcal{C}_T$ are the same as objects in $\mathcal{C}$ (e.g., sets in the category $Set$)
  • Morphisms $f: A \rightarrow B$ in $\mathcal{C}_T$ are morphisms $f: A \rightarrow T(B)$ in $\mathcal{C}$ (e.g., functions $f: A \rightarrow List(B)$ for the list monad)
• Composition of morphisms $f: A \rightarrow B$ and $g: B \rightarrow C$ in $\mathcal{C}_T$ is defined as $\mu_C \circ T(g) \circ f$
  • $f: A \rightarrow T(B)$ and $g: B \rightarrow T(C)$ are morphisms in $\mathcal{C}$
  • $T(g): T(B) \rightarrow T(T(C))$ applies the functor $T$ to the morphism $g$
  • $\mu_C: T(T(C)) \rightarrow T(C)$ is the multiplication natural transformation of the monad $T$
• Identity morphism $id_A: A \rightarrow A$ in $\mathcal{C}_T$ is given by the unit natural transformation $\eta_A: A \rightarrow T(A)$ of the monad $T$

Kleisli category vs monadic computations

• The Kleisli category $\mathcal{C}_T$ captures the composition of monadic computations
  • Monadic values are represented as morphisms in $\mathcal{C}_T$
    • A morphism $f: A \rightarrow B$ in $\mathcal{C}_T$ corresponds to a computation that takes a value of type $A$ and returns a monadic value of type $T(B)$ (e.g., $f: A \rightarrow List(B)$ for the list monad)
  • Composition of morphisms in $\mathcal{C}_T$ uses the multiplication $\mu$ of the monad, allowing for sequential composition of monadic computations
• The Kleisli category provides an abstract and compositional way to work with monadic computations without explicitly dealing with the monadic structure

Free Algebras

Free algebras of monads

• Given a monad $(T, \eta, \mu)$ on a category $\mathcal{C}$ and an object $X$ in $\mathcal{C}$, a free $T$-algebra on $X$ is a $T$-algebra $(T(X), \mu_X)$ together with a morphism $\eta_X: X \rightarrow T(X)$
• The universal property of free algebras states that for any other $T$-algebra $(A, h)$ and morphism $f: X \rightarrow A$, there exists a unique $T$-algebra homomorphism $f^*: (T(X), \mu_X) \rightarrow (A, h)$ such that $f^* \circ \eta_X = f$
• The free $T$-algebra $(T(X), \mu_X)$ is the "most general" or "least constrained" $T$-algebra that can be constructed from $X$

Construction of free algebras

• For the list monad $(List, \eta, \mu)$ on the category $Set$:
  1. Given a set $X$, the free algebra on $X$ is $(List(X), \mu_X)$
     • $List(X)$ is the set of all finite lists with elements from $X$
     • $\mu_X: List(List(X)) \rightarrow List(X)$ concatenates lists, flattening a list of lists into a single list
  2. The morphism $\eta_X: X \rightarrow List(X)$ maps each element $x \in X$ to the singleton list $[x]$
• The universal property ensures that for any other $List$-algebra $(A, h)$ and function $f: X \rightarrow A$, there exists a unique $List$-algebra homomorphism $f^*: (List(X), \mu_X) \rightarrow (A, h)$ such that $f^* \circ \eta_X = f$

Free algebras vs Kleisli category

• Free algebras and the Kleisli category are related through adjunctions
• The free $T$-algebra functor $F_T: \mathcal{C} \rightarrow \mathcal{C}_T$ maps an object $X$ in $\mathcal{C}$ to the free $T$-algebra $(T(X), \mu_X)$ in $\mathcal{C}_T$
• $F_T$ is left adjoint to the forgetful functor $U_T: \mathcal{C}_T \rightarrow \mathcal{C}$, which maps a $T$-algebra $(A, h)$ in $\mathcal{C}_T$ to its underlying object $A$ in $\mathcal{C}$
• The adjunction between $F_T$ and $U_T$ establishes a correspondence between free $T$-algebras in $\mathcal{C}_T$ and objects in $\mathcal{C}$
• The Kleisli category $\mathcal{C}_T$ can be seen as a category of free $T$-algebras, where morphisms are $T$-algebra homomorphisms between free $T$-algebras