Thursday, September 6, 2012

Monads I: Theory

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.

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 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 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]\]

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)\]
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.