MENTAL
 Main Menu
 Applications
 Computer Science
 Monads

Monads
 MONADS

The generalization of continuations

"The monad is nothing but a simple substance which enters into composite entities; simple, that is to say, without parts" (Leibniz. Monadology).


Monad in category theory

The concept of monad belongs to category theory.

A category consists of a class (a set of objects) and a set of morphisms. A morphism (or arrow) is a directed relation between two objects A and B of the class (a binary relation), which is expressed as A→B.

A category C satisfies the following two axioms:
  1. Associative composition of morphisms:
    h ο (g ο f) = (h ο g) ο f

  2. Morphism identity. For every object x of C there exists a morphism identity 1x which makes it correspond to itself.
A functor (or functor) is a function from one category to another that carries objects to objects and morphisms to morphisms so that the composition of morphisms and identities are preserved. An endofunctor is a functor of a category on itself.

A natural transformation transforms one functor into another while respecting its internal structure, i.e. the composition of morphisms, of the categories involved. It can be considered as a morphism of functors.

Having reviewed these concepts of category theory, we can give the formal definition of monad over a category C, also called "triple" because it is defined by three axioms: We can consider a monad as a category in which objects are states of a system and morphisms are transition functions between states.


Monads in functional programming languages

Since the key concept of category theory is that of morphism, monads are being applied in functional programming languages. These languages are of two types: The trend is to integrate both aspects in functional languages. One of the mechanisms used for this purpose is precisely the use of monads. Monads are used as a complementary mechanism for pure functional languages to support the imperative paradigm. In functional programming, a monad is a structure that represents a sequence of transformations of an object. To use monads in a functional language, it is not necessary to have prior knowledge of category theory.

The basic idea of a monad in functional programming is as follows: The monad function is also called a "container", since it contains the original function.


Monads in Haskell

Haskell [Bird, 2000], one of the best known pure functional languages, uses monads. In Haskell the three monad functions are reduced to two: return and bind (bind, bind). The latter is represented as ">>=".

In Haskell, by definition, M is a monad when it possesses the following two operations:
  1. return :: a → M a
    This operation admits several interpretations:

    • Is a container or monad M containing the basic value or type a.

    • The basic value or type a is of type M.

    • The monadic type M a represents a computation that produces the basic value or type a.

    For example, in the container interpretation, if I have an apple (a), I can put it in a box (M).

  2. (>>=) :: M a → (a → M b) → M b
    Combines two computations in sequence, passing the result of the first as an argument of the second. This operation is associative.

    The function (a → M b) is applied with the input value (M a), whose result is M(M b)) which is put together to obtain a container of type (M b).

    For example, if I have a box of apples (M a), and if for each apple I get a box of pears, then I can get a box with all pears together.
Haskell also defines the meta-function fmap, which applies a function f to all the elements of a container, such that the objects a, b, c, ... of the container are transformed into f(a), f(b), f(c), ... and morphisms of type a → b are transformed into f(a) → f(b). It is defined as follows: For example, if from each apple I get a pear (a → b), from a box of apples I get a box of pears (fa → fb).

The function fmap is a particular case of the so-called "lifting monadic", where basic values are replaced by monadic values, i.e., it generalizes a function by replacing arguments by containers. In general,

f(T1 … Tn) → r ⇒ f(MT1 ... MTn) → Mr

Monads transformed Haskell into an imperative programming language. Haskell popularized the use of monads for imperative programming with the notation do.


Monads vs. Continuations

A continuation can be expressed as follows: f(x, c) = c(f(x)), that is, the continuation c is a function that is a parameter of another function. For example, There is a close relationship between monads and continuations. In both cases an additional function must be specified: If monads are used, the specification of continuations becomes simpler, clearer and easier to maintain, since the whole program does not have to be modified, only the monads have to be redefined.

Eugenio Moggi [1989] has shown that the concept of monad is more general than that of continuation. In other words, a continuation is a particular case of a monad. The composition of continuations has monadic structure.


Monads, abstract algebra and universal algebra

A monad is essentially a monoid in an endophytic category. In abstract algebra, a monoid is an algebraic structure with an internal binary operation, which is associative and has a neutral element. That is, a monad is a semigroup with a neutral element. A semigroup is a set with an internal associative operation.

Universal algebra is a generalization of abstract algebra that studies the common and generic properties of all algebraic operations and structures on a set. It is a kind of algebraic meta-theory based on a small number of axioms.

Category theory and universal algebra aim at the grounding of all algebraic structures. Universal algebra is based on the internal operations that define the structure. Category theory is based on morphisms.

Universal algebra can be formulated in terms of category theory, in particular it can be defined in terms of monads. Therefore, with monads any algebraic structure can be constructed. There is an equivalence between universal algebra and monads in the category Sets (the category of sets). Monads allow to express in a compact form certain aspects of the universal algebra.

Monads provide a different view of universal algebra. For example, varieties can be represented by monads. Universal algebra is essentially the study of varieties. A manifold is a generalization of curve (1-manifold) and surface (2-manifold) to n dimensions.


Advantages and limitations of monads in pure functional languages

The advantages are: And the constraints are important:
Implementing Monads in MENTAL

Category theory vs. MENTAL

Category theory is a theory with a simple foundation (binary relations between objects). But paradoxically it is a complex theory, unnatural, too abstract and not very intuitive for two reasons: 1) because it is based on a single conceptual primitive (the morphism); 2) because this primitive is ambiguous, it has no defined semantics, it is open, since the concept of morphism admits many interpretations.

Moreover, category theory is unsuitable for grounding mathematics and unsuitable for application to programming. The true categories are the universal semantic primitives, which establish the degrees of freedom. [see Applications - Mathematics - Category Theory].


Monads vs. generic expressions

The concept of monad is so confusing that it has been attempted to be defined in many ways, including the following: It has even been claimed that the monad concept is ineffable, that it is not possible to define it and that we can only use it in concrete applications.

The definition that seems perhaps closest to the concept is the following: a monad is a design pattern for composing functions with extended types. An extended type is a more general type that includes the basic type.

However, this definition is not clear enough. Monads are really generic expressions in disguise. With MENTAL generic expressions the mechanisms of monads are simplified and clarified. Moreover, their limitations are overcome.
Examples

On the subject of the relationship between objects and transformations, there are two extreme processes:
  1. The same function is applied successively to several objects in a sequence. It corresponds to the fmap meta-function of some functional programming languages such as Haskell and Lisp. It is a higher-order function that applies the initial function to each element of a list, returning a list of results in the same order.

  2. The same object is subjected to several successive transformations.
In practice, these two types of processes can become confused, since a sequence of objects can be considered a single object.

These two processes can be specified in an extremely simple way in MENTAL.

In the first case, the meta-function fmap is expressed as follows:

⟨( (fmap f x) = ( ( [f([x↓])] ) )⟩
(f applies to each of the components of x)

Examples:
  1. ⟨( f(x) = x*x )⟩)
    (a = (1 2 3 4))
    (fmap f a) // ev. (1 4 9 16)

  2. ⟨( f(x) = (x x+10)↓ )⟩
    (a = (1 2 3 4))
    (fmap f a) // ev. (1 11 2 12 3 13 4 14)

  3. We want to subject a numerical sequence to a transformation such that each element of the sequence is transformed into two sequences:

      f: n → (n, n), (n+1, n+2).

    For example, if we have the object (1, 2, 3, 4), the result is.

      (1,1), (2,3), (2,2), (3,4), (3,3), (4,5), (4,4), (5,6)

    In MENTAL:

      ⟨( f(n) = ((n n n) (n+1 n+2))↓ )⟩

    This function converts a number into an open expression consisting of two sequences.

      (x = (1 2 3 4))
      (fmap f x) // ev.
      ((1 1) (2 3) (2 2) (3 4) (3 3) (4 5) (4 4) (5 6))
In the second case we have, for example, the functions: In this example, the functions can be chained together without problems. But there are times when chaining cannot be done mechanically when there are errors, for example, when trying to calculate the square root of a negative number. For example:

We define ⟨( fοg = g(f) )⟩ (composition of functions)
with the associative property:
⟨( (fοg)οh ≡ fο(gοh) )⟩.

For example,
(sqrt(r) ο sum5(r))
evaluates to (sum5(sqrt(r))),
being ⟨( sum5(r) = r+5 )⟩.

We assume that the function sqrt(r) returns the square root of r if r>0 or the text "error" if r<0. The following function must first check, before applying it, that the result of the previous function is a number and not an error message. If it detects the error message, its response must also be the same error message. The new function would be: This same mechanism should be applied to the following possible functions of the chain. In order not to repeat it, we can create a generic expression: Therefore, the concatenation expression of the two functions would be: In this example, two output values could be specified (the result of the function and a message indicating whether or not an error occurred.


Addenda

Origin of monads

The term "monad" is borrowed from Leibniz, just as the term "category" is borrowed from Kant. For Leibniz, a monad is a simple substance that is part of all elements of reality.

Saunders Mac Lane, co-founder of category theory, together with Samuel Eilenberg adopted the philosophical term "monad" to refer to something general, an entity capable of generating all other entities. But that does not mean that the monad is simple, for the concept of monad in category theory is very abstract, complex and unintuitive, and therefore goes against Leibniz's conception. The popularity of the term ¨monad" is probably due to Mac Lane himself for his influential book Category Theory for the Working Mathematician. It is also believed that the term "monad" was motivated and stimulated by its similarity to the word "monoid", for a monad is a monoid.

Monads have been known by other names: triple or triad (for their definition by three axioms) and standard construction (for their claim to be something that grounds everything else). The first monad to be constructed was presented by Roger Godemont in 1958 [Barr & Wells, 1985].

Eugenio Moggi [1989, 1990, 2000] was the first to introduce monads in computing, specifically in the area of denotational semantics [Stoy, 1997] to try to model their meaning. Denotational semantics is based on assigning to each language element a mathematical object.

Spivey [1990] found that monads provided an easy way to deal with exceptions.

Philip Wadler [1990, 1992, 1992, 1995, 1997] popularized Moggi's ideas by proposing monads as a general technique for extending functional languages to imperative programming.

Monads have been used in the development of the Glasgow Haskell compiler (which is written in Haskell).


Applications of monads

Monads are being applied, in various fields:
Predefined monads in Haskell

Haskell supplies predefined monads for use as functions and for combining functions.

MonadDescription
MaybeComputations that may or may not return a result
IdentityMónada identidad
[] (List)Computations returning multiple results
IOComputations that perform Input/Output
ErrorComputations that may fail or throw exceptions
StateComputations that maintain state
ReaderComputers reading data
WriterComputers that write data
ContComputers that can interrupt or restart themselves


Bibliography