Target audience: Advanced
Estimated reading time: 6'
Are you familiar with Category Theory, Monads, or Functors? Monads, in particular, are gaining popularity as functional languages like Clojure, Haskell, and Scala become more widely accessible.
This article marks the initial segment of our series, delving into the theory behind Monad implementation. The subsequent post, Don't fear the Monad: Scala will cover the practical implementation in Scala.
According to the dictionary:
"Monad: an elementary, fundamental substance that mirrors the structure of the world and serves as the foundation for deriving material properties."
In the realm of computer science, a Monad is a construct used to represent operations that can be either nested or chained for a specific data type. Consequently, software engineers can create pipelines to process data, with each step executing predefined rules defined by the monad. Monads are employed to handle tasks such as I/O operations, exceptions, and concurrency (or Futures).
Monads are grounded in the category theory, a field related to the more familiar group theory. The following section assumes some level of familiarity with mathematics, topology, and transformations.
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
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})\}\]
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.
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.