wiki:MonadicVedanta

The Monad Vedanta

My long fight with abstract bullshit (this is a technical term) is almost done.

"A Monad is Monoid in the category of Endofunctors"

To understand what is a Monad we have to understand the meaning behind of some abstract terms, namely, Functor, Endofunctor (which, it seems, is some specialization of a Functor) and a few more related abstractions.

We will use capitalized names for the core abstractions, analogous to the convention of capitalizing the names of types in Haskell (type-names and data-constructors must start with a capital letter). It also reflects the tendency of writing nouns capitalized in German. They were onto something.

A mathematical function, such as x => x+1 is often called a mapping, and the symbol => in this context (Math) stand for "maps to". So, this is a definition of an anonymous (nameless) function which maps x into x+1.

A Functor is an abstraction which generalizes such mappings (making them even more abstract) and therefore functions. Let's say that it abstracts out a transformation in general, not just for numbers or even sets, but in general.

A Functor is a generalized mapping (of a values) from one set to another (which could be the same set). This nonsense comes from the category theory, sort of mathematical tantrism (a politically correct name for a socially constructed and systematized utter bullshit) - you could be a guru (or a professor) and have a upper-middle class living out of preaching this nonsense.

The classic example could be the function ord which maps Characters into Integers (different types/sets of values).

  Prelude Data.Char> :i ord
  ord :: Char -> Int    -- Defined in ‘GHC.Base’
  Prelude Data.Char> ord 'a'
  97
  Prelude Data.Char>

The two types, namely Char and Int and the function ord, the whole setup together is said (by bullshitters) to form a Functor - a particular mapping between two particular sets. To be precise, they mean all the arrows together, this kind of an abstract mathematical structure - all the mappings from a to 97, from b to 98, for every pair of elements for each set.

It is also said (by bullshitters in CS) that a Function is a specialization (an instance of) a Functor, which at least for now, has no practical meaning. One could write whole series of blog posts (I am Jack's Endofuncor) about non-existent (or rather taken out of ones nose) connection between Category Theory and Computer Science, and so many do.

A generalized mapping over values in a Set (List or any other "collection") - the function that maps over the whole thing - is used to be implemented as a high-order function traditionally named map.

  map :: (a -> b) -> [a] -> [b]         -- Defined in ‘GHC.Base’

Tradition also uses homogeneous Lists as a canonical example of an ordered collection. This setup, however, is just a particular instance (specialization) of what is called a Functor. It is said that a List is an instance of a Functor for this very reason - having the map defined/implemented.

  instance Functor []       -- Defined in ‘GHC.Base’

A generalized, abstract map (an Interface) in the context of Functor abstraction is traditionally called fmap

  fmap :: (a -> b) -> f a -> f b    -- Defined in ‘GHC.Base’

and to be a Functor (to be viewed and used as a Functor) is to implement this fmap function (according to some well-defined constraints or laws).

From a programming language's point of view we have to hold a value somewhere (in a "concrete" collection which is usually called a container) so we could map over it - map (transform) values for one type to another (or the same type)

A partially applied function, a thunk or any other kind of a Lexical Closure could , at least in principle, be mapped over (because technically it captures values of all of its free variables, if any). It does not have to be a List or a Set.

To go ahead we have to understand, that functions are also first-class values, and partially applied functions are values of a different type (partial application literally transforms them).

  Prelude Data.Char> :t (+1)
  (+1) :: Num a => a -> a
  Prelude Data.Char> :t map (+1)
  map (+1) :: Num b => [b] -> [b]
  Prelude Data.Char>

Partially applied map yields a function on containers - in this case - on Lists.

But why?

In theory, a Functor is a set of mappings between collections (all of them). The map function (in the context of a programming language) deals with a particular container (it knows the actual implementation details). It accepts a transforming function on values which maps single values (NOT whole things) of one particular type into another as parameter and yields, when partially applied a function on whole things.

This means that any particular container together with its own implementation of the map function could be viewed as (an instance of) a Functor. Ok.

Monad

A Monad is a specialization of a Functor. That means it is a Mapping between two Sets of values or (in the context of a pure functional programming language) between two types (which is classically viewed as sets of all possible values, such as Integers).

Monoid

Now what is a Monoid? Monoid is another specialization of a Functor. It is an abstract mathematical structure, which consist of a binary operator and an identity element. Just this kind of structure, no more, no less.

It is said (by mathematicians) that Integers form a Monoid under addition.

The binary operator, the transformation which we call addition, it the mapping of a partially applied +. One could see 2+2 as a mapping of (+2) (partially applied +) over 2.

This, by the way, is what Smalltalk got right - just send a message +2 to an object 2. This, by the way, is no bullshit.

Multiplication (the * operator) with 1 (the identity element) is the same thing (a Monoid.

Folding

The only practical aspect of a Monoid lies in the context of folding of a collection. A particular container (or a collection) is Foldable only if it forms a Monoid (has an identity value, and a mapping function).

  sum = fold (+) 0
  product = fold (*) 1

In the context of CS folding encapsulates a recursive traversal of a collection (which could be empty). the identity elements is used in the base case and the binary operator is applied on each recursive call.

To be a Foldable is a nice property for a collection. Lexical Closures could be Foldable.

Bullshit all the way down

An Endofunctor is a Functor for which the result of a mapping has exactly the same type as the original. In the context of functional programming all the mapping within the same type of a container form an Endofunctor (they don't).

A Category is a grouping of all mappings. Think of a all the possible mappings of (+1), (+4), (+x) over an Integer (the set of all Integers). All these infinite many mappings form a Category (what a bullshit!). This Category describes a particular Endofunctor (in this case of addition of Integers).

Now lets stack up all the abstractions. A Monad is a Monoid. This means it is a collection (in Mathematical terms) together with a binary operation and an identity function (a Constant could be viewed as a Function - maps everything to a single value).

It is also a Semigroup which means that these things are Composable (could be morphed together or concatenated). Endofunctor means that we will always stay within the same collection (type).

So, why the fuck?!

Well, because type-safe composition of an abstract containers which could be mapped over. But why shall we do addition as mapping of partially applied + over some Integer inside a Monad?

Because it a pure-functional language this is the way to encapsulate (abstract out) a state and actions which cause side-effects.

But this is a merely useless wrapping?

Yes. In a strict (call-by-value) functional language all this is just a useless wrapping. Algebraic data types will do. There is no meaning in forming a Monad instead of defining a plain ADT (Abstract Data Type = a named set of interfaces). And this is the whole point.

However, in a lazy (call-by-need) pure-functional language this is the way to ensure an explicit order of evaluation, which is achieved by explicitly nesting a transformer function inside of the map (for a particular container, which could be always of the size of 1, why not?). This nesting ensures the order - map (or bind in the context of a Monad type-class) is implemented as nested functions -- it all boils down to this.

The static type-system guarantees that the whole chain is always within the same type, as it is supposed to be within an Endofunctor.

So, in Haskell in particular, IO is Monadic, which means, each value is wrapped inside a particular instance of a Monad (a container of size 1) and must be explicitly and rigorously composed and mapped over. Yes, IO operations are mapped over values. Just this.

Last modified 17 months ago Last modified on Jul 6, 2019, 12:32:46 PM
Note: See TracWiki for help on using the wiki.