Monad Basics

Motivation

The quest for defining what is a Monad has created a large amount of confusing blog posts, metaphors and misleading comparisons. This website is meant to simply provide a correct definition without trying to make it more accessible.

Although these definitions are abstract in nature and can be applied to many fields and disciplines, here we focus on their application to programming.

A monad is an idea with laws. It is an endofunctor with two natural transformations called unit and join. A monad is also an applicative functor. An applicative functor must abide monoidal laws. A monoid is also a semigroup.

The following pages will define each categorical structure and law that make up a monad.

All type definitions are written in Haskell.

Semigroup

In abstract algebra, a semigroup is a non-empty set with an associative binary operation.

Type definitions


(<>) :: a -> a -> a
mappend :: a -> a -> a

Laws


Associativity
(a <> b) <> c ≅ a <> (b <> c)

Monoid

A monoid is a semigroup with a unit element, therefor, it has the same binary operation from semigroup, mappend, and adds a unit function mempty.

For every object m in category M, binary operation p and unit element u the equation p(u, m) = m = p(m, u) must hold true for every monoid. In practical terms, a set of natural numbers N with a binary operation addition (+) and a unit element zero is a monoid.

Type definitions


(<>) :: a -> a -> a
mappend :: a -> a -> a
mempty :: m

Laws


Associativity
(a <> b) <> c ≅ a <> (b <> c)

Identity
(id <> u) ≅ u

Functor

Functors are structure preserving morphisms between categories. A functor F: A -> B maps each object a from category A to an object Fa in category B. Category A in functor F is called the domain and category B is the codomain.

Functors where the domain and codomain are the same category are called endofunctors. A functor F: A -> B is called a covariant functor, whereas a contravariant functor F: A^op -> B reverses each arrow resulting in F_f : F_b -> F_a.

Type definitions


(<$>) :: a -> b -> f a -> f b
fmap :: a -> b -> f a -> f b

contramap :: a -> b -> f b -> f a

Laws


Identity
(id <$> x) ≅ x

Composition
(f . g <$> x) ≅ (f <$> (g <$> x))

Applicative Functor

An applicative functor is a lax monoidal functor. It must follow functor and monoidal laws. It provides the pure and <*> (pronounced apply) functions. Pure is used to lift a pure function f to an applicative functor F_f.

Apply is a binary function used to sequence computations.

Type definitions


pure :: (a -> b) -> f (a -> b)
<*> :: f(a -> b) -> f a -> f b

Laws


Associative composition
((.) <$> a <*> b <*> c) ≅ (a <*> (b <*> c))

Identity
pure id <*> x ≅ x

Homomorphism
pure f <*> pure x ≅ pure (f x)

Composition
pure (.) <*> u <*> v <*> w ≅ u <*> (v <*> w)

Monad

A monad, also known as a triple, is an endofunctor with two natural transformations join and unit. A natural transformation is a mapping of two functors and such mapping can only exist if both functors have the same domain and codomain. The natural transformation join acts as the binary operation of a monad corresponding to the structure of a monoid.

The left and right unit laws as well as the associativity law must hold true for the structure to be a monad.

Type definitions


return :: a -> m a
join :: m (m a) -> a
>>= :: (a -> m b) -> m a -> m b

Laws


Associativity
g >>= (f >>= x) ≅ ((g >>=) . f) >>= x