Target audience: Advanced
Estimated reading time: 30'
Monads are becoming popular with the democratization of functional languages such as Closure, Haskell and Scala. The dictionary provides the following definition:
Monad: an elementary individual substance which reflects the order of the world and from which material properties are derived.
In computing science a Monad is a structure that represents operations either nested or chained on a specific type. Consequently software engineers can build pipelines to process data for which each step execute some predefined rules, defined by the Monad. Monad are used to pipe I/O operations, exceptions, concurrency (or Futures).
Monads relies on the Categories Theory which is a related to the more known Group Theory. The following section assumes the reader has some knowledge of mathematics, topology and transforms.
Monoids
A monoid is a structure
(S,*,1) consisting of an associative binary operation * over some set S, which contains an identity element 1 for \[\forall s_{i}\in S\,\,\, s_{i}*s_{j} \in S\\(s_{i}*s_{j})*s_{k} = s_{i}*(s_{j}*s_{k})\\1*s_{i} = s_{i}*1=s_{i}\]Categories
Categories are a generalization of monoids. A category consists of objects and morphisms. A morphism is a transformation that operates on objects. Let's consider a morphism f, related to objects x and y: \[f: x \mapsto y\] Morphisms have the following properties
* Transitivity: \[f: x \mapsto y\,\,,\,g: y \mapsto z\,\Rightarrow f\circ g: x \mapsto z\] * Omnipotence: \[id:x \mapsto x\] * Associativity: \[f\circ (g\circ h) = (f\circ g) \circ h\]
Sets, Arrays, Vectors, Matrices, Lists or Hash tables constitute category which support morphism. Let consider two operations, sqr and log on arrays of floating point values x: \[sqr : \{x_{i}\} \mapsto \{x_{i}^2 \} \,\,\, log : \{y_{i}\} \mapsto \{log(y_{i})\}\,\,\,\Rightarrow \,\, sqr \circ log : \{x_{i}\} \mapsto \{2.log(x_{i})\}\]
Functors
Functors are a special class of morphisms called homomorphisms. A Functor F define a structure-preserving mapping, between two categories, X and Y, F: X->Y. If f and g are operations on object on categories X/Y, 1 the identity function then \[f: x\in X \mapsto y \in Y,\,\,\,F:X \mapsto Y \Rightarrow F(f): F(x) \mapsto F(y)\\ F(1_{x}) = 1_{F(x)}\\ F(f \circ g) = F(f) \circ F(g)\] A functor that maps a category to itself is called an endofunctor. A endofunctor, denoted as 1x, maps every element and morphism of X to itself
.Natural Transformation
Natural transformations are mappings, from one functor to another. Let's denote two Functors F, G between two categories X, Y. A natural transformation phi between F & G is defined as \[\phi[x\in X]: F(x) \mapsto G(x)\\ \forall f \in F : x \mapsto y\,\,,\phi[y] \circ F(f) = G(f) \circ \phi[x]\]
Natural transformations are mappings, from one functor to another. Let's denote two Functors F, G between two categories X, Y. A natural transformation phi between F & G is defined as \[\phi[x\in X]: F(x) \mapsto G(x)\\ \forall f \in F : x \mapsto y\,\,,\phi[y] \circ F(f) = G(f) \circ \phi[x]\]
Monads
A monad T = <T,1,m> on a category X consists of
- A endofunctor T on category X T:X->X
- A unit natural transformation n: 1 -> T
- A join (or multiplication) natural transformation mu: T*T -> T
A monad obeys to the associativity axiom:\[If\,\, T^{2}(X) = T \circ T (X)\,\,and\,\, T^{3}(X) = T \circ T \circ T (X)\\T(\mu X) : T^{3}(X) \mapsto T^{2}(X)\\\mu X : T^{2}(X) \mapsto T(X)\\\mu T(X) : T^{3}(X) \mapsto T^{2}(X)\] as well as the unit axiom: \[T(\eta X) : T(X) \mapsto T^{2}(X)\\\eta T(X) : T(X) \mapsto T^2(X)\\ I_{X} : T(X) \mapsto T(X)\]
Example
Let's consider the category, list of integer denoted List<Integer>. The monad related to the List<Integer> category is defined as \[Square : List \left \langle Int \right \rangle \mapsto List \left \langle Int\right \rangle\,\,\,\,\,\,\,\left \{ .. x .. \right \} \mapsto \left \{ .. x^{2} .. \right \}\\\eta : x \mapsto List\left \{ x \right \}\\\mu : List(List\left \langle Int \right \rangle ) \mapsto List \left \langle Int \right \rangle \,\,\left \{ \left \{ x_{0} .. x_{n}\right \}, \left \{y_{0} ..y_{m} \right \} \right \} \mapsto \left \{ x_{0},y_{0} .. x_{n},y_{n} .. y_{m} \right \}\] Monads are used to manage sequence of computations.
- Exception: may throw exceptions or generated known errors.
- Option: may fail or return a result
- State: may use mutable state
- Reader: may maintain a context during computation
- Writer: may produce side-effect during computation
- I/O: may success or fails depends on global state or variables.
A monad T = <T,1,m> on a category X consists of
- A endofunctor T on category X T:X->X
- A unit natural transformation n: 1 -> T
- A join (or multiplication) natural transformation mu: T*T -> T
A monad obeys to the associativity axiom:\[If\,\, T^{2}(X) = T \circ T (X)\,\,and\,\, T^{3}(X) = T \circ T \circ T (X)\\T(\mu X) : T^{3}(X) \mapsto T^{2}(X)\\\mu X : T^{2}(X) \mapsto T(X)\\\mu T(X) : T^{3}(X) \mapsto T^{2}(X)\] as well as the unit axiom: \[T(\eta X) : T(X) \mapsto T^{2}(X)\\\eta T(X) : T(X) \mapsto T^2(X)\\ I_{X} : T(X) \mapsto T(X)\]
Example
Let's consider the category, list of integer denoted List<Integer>. The monad related to the List<Integer> category is defined as \[Square : List \left \langle Int \right \rangle \mapsto List \left \langle Int\right \rangle\,\,\,\,\,\,\,\left \{ .. x .. \right \} \mapsto \left \{ .. x^{2} .. \right \}\\\eta : x \mapsto List\left \{ x \right \}\\\mu : List(List\left \langle Int \right \rangle ) \mapsto List \left \langle Int \right \rangle \,\,\left \{ \left \{ x_{0} .. x_{n}\right \}, \left \{y_{0} ..y_{m} \right \} \right \} \mapsto \left \{ x_{0},y_{0} .. x_{n},y_{n} .. y_{m} \right \}\] Monads are used to manage sequence of computations.
- Exception: may throw exceptions or generated known errors.
- Option: may fail or return a result
- State: may use mutable state
- Reader: may maintain a context during computation
- Writer: may produce side-effect during computation
- I/O: may success or fails depends on global state or variables.
