loading...

Monad is Monoid - explained without math

ingun37 profile image Ingun 전인건 Updated on ・4 min read

Motivation

In this post I will try to explain why monad is monoid in programmer’s perspective without mathematical prerequisites.

Before I begin I want to encourage you by showing that it’s not difficult at all, in fact, is just around the corner.

Let’s compare the two definitions side by side. You don’t need to understand them, just see how they looks.

Monadμ::T2Tη::ITμ(T,μ(T2))=μ(μ(T2),T)μ(η(I),T)=μ(T,η(I))=TMonoid::T×TTit1(t2t3)=(t1t2)t3it=ti=t \begin{aligned} &\text{Monad} \\ &\mu :: T^2 \rightarrow T \\ &\eta :: I \rightarrow T \\ &\mu(T,\mu(T^2)) = \mu(\mu(T^2),T) \\ &\mu(\eta(I),T) = \mu(T,\eta(I)) = T \\ \end{aligned} \hspace{1em} \begin{aligned} &\text{Monoid} \\ &\otimes :: T \times T \rightarrow T \\ &i \\ &t_1 \otimes (t_2 \otimes t_3) = (t_1 \otimes t_2) \otimes t_3 \\ &i \otimes t = t \otimes i = t \\ \end{aligned}

Do you see the similarities?
Let’s see in the other point of view.

Monad1ηTT2μTT×1Tid×ηT2μTη×id1×TTT3id×μT2μ×idμT2μT \text{Monad} \\ \text{}\\ \begin{gathered} 1 \\ \darr_{\eta} \\ T \\ \end{gathered} \hspace{1em} \begin{gathered} T^2 \\ \darr_{\mu} \\ T \\ \end{gathered} \hspace{1em} \begin{gathered} T \times 1 \\ \darr \\ T \\ \end{gathered} \begin{gathered} \xrightarrow{id\times\eta} \\ \\ \rightarrow \\ \end{gathered} \begin{gathered} T^2 \\ \darr_{\mu} \\ T \\ \end{gathered} \begin{gathered} \xleftarrow{\eta\times id} \\ \\ \leftarrow \\ \end{gathered} \begin{gathered} 1 \times T \\ \darr \\ T \\ \end{gathered} \hspace{1em} \begin{gathered} T^3 \\ \darr_{id \times \mu} \\ T^2 \\ \end{gathered} \begin{gathered} \xrightarrow{\mu\times id} \\ \\ \xrightarrow{\mu} \\ \end{gathered} \begin{gathered} T^2 \\ \darr_{\mu} \\ T \\ \end{gathered}
Monoid1idTT×TTT×1T1×idT×TTid×11×TTT×T×T1×T×T×1T×TT \text{Monoid} \\ \text{}\\ \begin{gathered} 1 \\ \darr_{id} \\ T \\ \end{gathered} \hspace{1em} \begin{gathered} T\times T \\ \darr_{\otimes} \\ T \\ \end{gathered} \hspace{1em} \begin{gathered} T \times 1 \\ \darr \\ T \\ \end{gathered} \begin{gathered} \xrightarrow{1\times id} \\ \\ \rightarrow \\ \end{gathered} \begin{gathered} T \times T \\ \darr_{\otimes} \\ T \\ \end{gathered} \begin{gathered} \xleftarrow{id \times 1} \\ \\ \leftarrow \\ \end{gathered} \begin{gathered} 1 \times T \\ \darr \\ T \\ \end{gathered} \hspace{1em} \begin{gathered} T\times T\times T \\ \darr_{1 \times \otimes} \\ T\times T \\ \end{gathered} \begin{gathered} \xrightarrow{\otimes\times 1} \\ \\ \xrightarrow{\otimes} \\ \end{gathered} \begin{gathered} T\times T \\ \darr_{\otimes} \\ T \\ \end{gathered}

Similarity is striking! No doubt they must be the same thing at some level! Once you know which property of Monad corresponds to Monoid’s, you will see the oneness.

Monad <-> Monoid

Monad is probably most familiar to programmers as following definition:

μ(T2)Tη(I)T \mu(T^2) \rightarrow T \newline \eta(I) \rightarrow T

μ\mu ‘s widely known as join, and η\eta as return to programmers. TT is a monad type, T2T^2 is type composition e.g List2\text{List}^2 would be a List of List

Of course mere existence of functions of the signature won’t automatically turn T into a monad. There are additional laws need to be fulfilled. It seems like they don’t get enough attention they deserve from programmers probably because currently (as far as I know) there’s no compiler that can impose those laws on monad type. But you need to know them because the monadic laws are the ones who corresponds to the monoid’s associativity and identity.

Monad’s Join = Monoid’s Associativity

Monadic law on μ\mu is:

μ(T,μ(T2))=μ(μ(T2),T) \mu(T,\mu(T^2)) = \mu(\mu(T^2),T)

It means no matter which pair of T you join first you will get same result. Take List as example. For List to be a monad, it must have join defined that list<list<list>>.join().join() and list<list<list>>.map(join).join() yields the same result.

This law is the one who corresponds to Monoid’s associativity.

(t1t2)t3=t1(t2t3) (t_1 \otimes t_2) \otimes t_3 = t_1 \otimes (t_2 \otimes t_3)

Hope this picture gives you better view at it.

Alt Text

Monad with μ\mu as monoid operator conforms to monoid’s associativity.

Three Ts in monad are waiting in line to be evaluated (resolved) into another type. No matter which pair (left or right) gets evaluated first the result will be same by monadic law. This property of monad exactly corresponds to monoid’s associativity. Three Ts in monoid are waiting in line to be evaluated (calculated) into another algebraic value. It as well doesn’t matter which pair gets evaluated first because they are associative by definition of monoid.

Monad’s Return = Monoid’s Identity

Law on η\eta (aka return) is:

μ(η(I),T)=μ(T,η(I)) \mu(\eta(I),T) = \mu(T,\eta(I))

It means μ\mu must yield same result when given either T of results of η\eta or result of η\eta on T. Again, take List as example. For List to be a monad list.map(return).join() and return(list).join() must yield same result. Law of η\eta corresponds to monoid’s identity.

it=ti=t i \otimes t = t \otimes i = t

Alt Text

Hope this picture gives you a clear view at it.

η\eta conforms monoid’s identity property.

You may wondering, wait, η\eta is a function! How could a function serve as a identity object?
It’s because applying η\eta to the entire TxTx or to only xx corresponds to the act of multiplying (which can be defined as function) identity object left and right respectively.

Conclusion

Monad is monoid of generic type with one polymorphic parameter.

If you want further learning material on this topic checkout Category Theory for Programmer - Monads Categorically.
If you want to learn category theory these are excellent materials:
Category Theory for Programmers
Math3ma - Category Theory
These are my original solutions to Challenges from Category Theory for Programmers: ingun37.github.io/answers/

Posted on by:

ingun37 profile

Ingun 전인건

@ingun37

🇰🇷Developer/Mathematics Enthusiast

Discussion

markdown guide