Thursday, September 6, 2012

Monads I: Theory

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

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. 

References
- Video introduction to Monads - Eugenia Cheng - University of Texas 2007
- Overview Monads M. Baker

2 comments:

  1. I can only express a word of thanks! Nothing else. Because your topic is nice, you can add knowledge. Thank you very much for sharing this information.

    Avriq India
    avriq
    pest control
    cctv camera

    ReplyDelete
  2. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. machine learning projects for final year In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.


    The Nodejs Training Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

    ReplyDelete