202207271324 Creating a monad from a set

Say we have a set ($M$). What would make that set a monoid?

Our first step to Monads is to make the set a Magma. A magma is a set that has any binary operator ( $\cdot$ ) that takes two elements of that set and produces another element in that set.

$$a,b \in M \implies a \cdot b \in M$$

Next, we add associativity to turn our Magma into a Semigroup.

$$\forall a,b,c \in M \enspace [(a \cdot b) \cdot c = a \cdot (b \cdot c)]$$

Next, we add the identity constraint to turn our Semigroup into a Monoid.¹ Note that we specify the "left" and "right" identity since we don't have the commutativity constraint.

$$\exists i \in M \enspace [\forall x \in M : | : i \cdot x = x \land x \cdot i = x]$$

Notice also that as a category, a monoid contains only one item (hence the "mon-" prefix). All morphisms loop back onto the same object. This is an english language way of saying the same associativity and identity ideas.

This is where we take a turn away from sets. The (in)famous saying

A monad is just a monoid in the category of endofunctors.

shows that we need to look at the monoid through the lens of a functor to create a monad.²

Refreshing our knowledge of Functors and Applicatives

class Functor f where
    fmap :: (a -> b) -> f a -> f b

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

We extend those to include bind (or join or >>=). This function is defined as the act of applying a monad (m a) to a function that takes a value and returns a monad ((a -> m b)) to produce another monad (m b).

class (Applicative m) => Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

Now we need to ensure the "left" and "right" identity and associativity work for our monad to make sure that it really is a Monad (and also where we confirm our connection to the monoid).

-- a value in default context fed to a function = applying the function to the value
return x >>= f = f x

-- a monadic value fed to return just gives us that same value
m >>= return = m

-- nesting doesn't matter when chaining monadic function applications with bind
(m >>= f) >>= g = m >>= (\x -> f x >>= g)

In a more obvious form, but using Kleisli-composition operator

infixr 1 >=>
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g =  \x -> f x >>= g -- simply composition of monadic functions

-- return becomes more obviously the identity function
-- composition becomes more obviously the binary operation
return >=> f = f                  -- return composed with f is f
m >=> return = m                  -- f composed with return is f
(m >=> f) >=> g = m >=> (f >=> g) -- order of composition doesn't matter

So this shows that we have a "set" with binary operation (for product monoid multiplication and for monad functor composition) that follows the associativity and identity (for product monoid 1 and monad "return" or the identity function) constraints.

Monads have to be "fixed" to a specific functor whereas monoids are defined for any functor.

Finally, we can put forward a mostly rigorous way that a monad is made from a monoid.³

• The monoid set ($M$) is replaced by the endofunctor $T : X \rightarrow X$
• The binary operation ($\mu : M \cdot M \rightarrow M$) is replaced by the natural transformation $\mu : T \cdot T \rightarrow T$
• The unit/identity element ($\eta : 1 \rightarrow M$) is replaced by the natural transformation $\eta : I_x \rightarrow T$