This is a continuation of Monads for high school I and Monads for High School II: Lists. This post covers the concept of algebras for the monad for lists.
To manipulate the demos in this post, you must have Wolfram CDF Player installed on your computer. It is available free from the Wolfram website. The code for the demos is in the Mathematica notebook MonadAlg.nb
Lists
$\textrm{Lists}(S)$ is the set of all lists of finite length whose entries are elements of $S$.
-
$\boxed{2\; 2\; 4}$ is the way I denote the list of length $3$ whose first and second entries are each $2$ and whose third entry is $4$.
-
A list with only one entry, such as $\boxed{2}$, is called a singleton list.
-
The empty list $\boxed{\phantom{2}}$ has no entries.
- $\textrm{Lists}^*(S)$ is the set of all nonempty lists of finite length whose entries are elements of $S$.
- $\textrm{Lists}(\textrm{Lists}(S))$ is the list whose entries are lists with entries from $S$.
- For example, $\boxed{\boxed{5\; 7}\; \boxed{2\; 12\; 7}}$ and $\boxed{\boxed{5\; 7\; 2\; 12\; 7}}$ are both entries in $\textrm{Lists}^*(\textrm{Lists}^*(\mathbb{Z}))$. The second one is a singleton list!
- $\boxed{\boxed{\phantom{3}}\; \boxed{2}}
$ and $\boxed{\boxed{\phantom{3}}}$ are entries in $\textrm{Lists}^*(\textrm{Lists}(\mathbb{Z}))$.
- The empty list $\boxed{\phantom{2}}$ is an entry in $\textrm{Lists}(\mathbb{Z})$, in $\textrm{Lists}(\textrm{Lists}^*(\mathbb{Z}))$ and in $\textrm{Lists}(\textrm{Lists}(\mathbb{Z}))$. If you have stared at this for more than ten minutes, do something else and come back to it later.
The star notation is used widely in math and computing science to imply that you are including everything except some insignificant shrimp of a thing such as the empty list, the empty set, or $0$. For example, $\mathbb{R}^*$ denotes the set of all nonzero real numbers.
More details about lists are in Monads for High School II: Lists.
Join
The function join (or concatenation) takes two lists and creates a third list. For example, if you join $\boxed{5\; 7}$ to $\boxed{2\; 12\; 7 }$ in that order you get $\boxed{5\; 7\; 2\; 12\; 7}$.
- I will use this notation: join$\boxed{\boxed{5\; 7}\; \boxed{2\; 12\; 7}}=\boxed{5\; 7\; 2\; 12\; 7}$.
- This notation means that I am regarding join as a function that takes a two-element list in $\textrm{Lists}(\textrm{Lists}(S))$ to an element of $\textrm{Lists}(S)$.
-
join removes one level of lists
-
join is not commutative: join$\boxed{\boxed{2\; 12\; 7}\; \boxed{5\; 7}}=\boxed{2\; 12\; 7\; 5\; 7}$
-
Join is associative, and as for any associative binary operation, join is defined on any finite list of lists of elements of $S$. So for example, join$\boxed{\boxed{5\; 7}\; \boxed{2\; 12\; 7}\; \boxed{1}}=\boxed{5\; 7\; 2\; 12\; 7\; 1}$.
-
For any single list $\boxed{a\; b\; c}$, join$\boxed{\boxed{a\; b\; c}}=\boxed{a\; b\; c}$. This is required to make the theory work. It is called the oneidentity property.
-
If the empty list $\boxed{\phantom{2}}$ occurs in a list of lists, it disappears when join is applied: join $\boxed{\boxed{2\; 3}\; \boxed{\phantom{2}}\; \boxed{4\; 5\; 6}}=\boxed{2\; 3\; 4\; 5\; 6}$.
More details about join in Monads for High School II: Lists.
The main monad diagram
When you have a list of lists of lists, join can be applied in two different ways, "inside" and "outside" as illustrated in the diagram below. It gives you several different inputs to try out as a way to understand what is happening.
This is the special case of the main diagram for all monads as it applies to the List monad.
As you can see, after doing either of "inside" and "outside", if you then apply join, you get the same list. That list is simply the list of entries in the beginning list (and the two intermediate ones) in the same order, disregarding groupings.
From what I have just written, you must depend on your pattern recognition abilities to learn what inside
and outside
mean. But both can also be described in words.
-
The lists outlined in black are lists of elements of $\mathbb{Z}$. In other words, they are elements of $\textrm{Lists}(\mathbb{Z})$.
- The lists outlined in blue are lists of elements of $\textrm{Lists}(\mathbb{Z})$. In other words, they are list of lists of elements of $\mathbb{Z}$. Those are the kinds of things you can apply join to.
- The leftmost list in the diagram, outlined in green, is a list in $\textrm{Lists}(\textrm{Lists}(\mathbb{Z}))$. This means you can apply join in two different ways:
-
Each list boxed in blue is a list of lists of integers (two of the are singletons!) so you can apply join to each of them. This is joining inside first.
-
You can apply join directly to the leftmost list, which is a list of lists (of lists, but forget that for the moment), so you can apply join to the blue lists. This is join outside first.
To understand this diagram, staring at the diagram (for most people) uses the visual pattern recognition part of your brain (which uses over a fifth of the energy used by your brain) to understand what inside and
outside
mean, and then check your understanding by reading the verbal description. Starting by reading the verbal description first does not work as well for most people.
The unit monad diagram
There is a second unitary diagram for all monads:
The two right hand entries are always the same. Again, I am asking you to use your pattern recognition abilities to learn what singleton list
and singleton each
mean.
The main and unit monad diagrams will be used as axioms to give the general definition of monad. To give those axioms, we also need the concepts of functor and natural transformation, which I will define later after I have finished the monad algebra diagrams for Lists and several other examples.
Algebras for the List monad
If you have any associative binary operation on a set $S$, its definition can be extended to any nonempty list of elements (see Monads for High School I.)
Plus and Times are like that:
-
$(3+2)+4$ and $3+(2+4)$ have the same value $9$, so you can write $3+2+4$ and it means $9$ no matter how you calculate it.
-
I will be using the notation Plus$\boxed{3\; 2\; 4}$ instead of $3+2+4$.
-
Times is also associative, so for example we can write Times$\boxed{3\; 2\; 4}=24$.
-
Like join, we require that these operations satisfy oneidentity, so we know Plus$\boxed{3}=3$ and Times$\boxed{3}=3$.
-
When the associative binary operation has an identity element, you can also define its value on the empty list as the identity element: Plus$\boxed{\phantom{3}}=0$ and Times$\boxed{\phantom{3}}=1$. I recommend that you experiment with examples to see why it works.
An algebra for the List monad is a function algop:$\textrm{Lists}(S)\to S$ with certain properties: It must satisfy the Main Monad Algebra Diagram and the Unit Monad Algebra Diagram, discussed below.
The main monad algebra diagram
Example using Plus and Times
The following interactive diagram allows you to see what happens with Plus and Times. Afterwards, I will give the general definition.
Plus insides replaces each inside list with the result of applying Plus to it, and the other operation Join is the same operation I have used before.
The main monad algebra diagram requires that if you have a list of lists of numbers such as the one below, you can add up each list (Plus insides) and then add up the list of totals (top list in diagram), you must get the same answer that you get when you join all the lists of numbers together into one list (bottom list in the diagram) and then add up that list.
This is illustrated by this special case of the main monad algebra diagram for Plus:
General statement of the main monad algebra diagram
Suppose we have any function $\blacksquare$ $:\textrm{Lists}(S)\to S$ for any set $S$.
If we want to give the main monad algebra diagram for $\blacksquare$ we have a problem. We know for example that Plus$\boxed{1\; 2}=3$. But for some elements $a $ and $b$ of $S$, we don’t know what $\blacksquare\boxed{a\; b}$ is. One way to write it is simply to write $\blacksquare\boxed{a\; b}$ (the usual way we write a function). Or we could use tree notation and write
.
I will use tree notation mostly, but it is a good exercise to redraw the diagrams with functional notation.
Main monad diagram in prose
Below is a presentation of the general main monad algebra diagram using (gasp!) English phrases to describe the nodes.
The unit monad algebra diagram
Suppose $\blacksquare$ is any function from $\textrm{Lists}(S)$ to $S$ for any set $S$. Then the diagram is
This says that if you apply $\blacksquare$ to a singleton you get the unique entry of the singleton. This is not surprising: I defined above what it means when you apply an operation to a singleton just so this would happen!
A particular example
These are specific examples of the general main monad algebra diagram for an arbitrary operation $\blacksquare$:
These examples show that if $\blacksquare$ is any function from $\textrm{Lists}(S)$ to $S$ for any set $S$, then
equals
and
equals
Well, according to some ancient Greek guy, that means
equals
which says that
is an associative binary operation!
The mother of all associative operations
We also know that any associative binary $\blacksquare$ on any set $S$ can be extended to a function on all finite nonempty lists of elements of $S$. This is the general associative law and was discussed (without using that name) in Monads fo High School I.
Let’s put what we’ve done together into one statement:
Every associative binary operation $\blacksquare$ on a set $S$ can be extended uniquely to a function $\blacksquare:\textrm{Lists}^*(S)\to S$ that satisfies both the main monad algebra diagram and the unit monad algebra diagram. Furthermore, any function $\blacksquare:\textrm{Lists}^*(S)\to S$ that satisfies both the main monad algebra diagram and the unit monad algebra diagram is an asssociative binary operation when applied to lists of length $2$ of elements of $S$.
That is why I claim that the NonemptyList monad is the mother of all associative binary operations.
I have not proved this, but the work in this and preceding posts provide (I think) a good intuitive understanding of this fundamental relationship between lists and associative binary operations.
Things to do in upcoming posts
-
I have to give a proper definition of monads using the concepts of functor and natural transformation. I expect to do this just for set functors, not mentioning categories.
-
Every type of binary operation that is defined by equations corresponds to a monad which is the mother of all binary operations of that type. I will give examples, but not prove the general case.
Other examples of monads
-
Associative binary operations on $S$ with identity element (monoids) corresponds to all lists, including the empty list, with entries from $S$.
-
Commutative, associative and idempotent binary operations, like and and or in Boolean algebra, correspond to the set monad: $\text{Sets}(S)$ is the set of all finite and countably infinite sets of elements of $S$. (You can change the cardinality restrictions, but you have to have some cardinality restrictions.) Join is simply union.
- Commutative and associative binary operations corresponds to the multiset monad (with a proper definition of join) and appropriate cardinality restrictions. You have to fuss about identity elements here, too.
-
Various kinds of nonassociative operations get much more complicated, involving tree structures with equivalence relations on them. I expect to work out a few of them.
-
There are lots of monads in computing science that you never heard of (unless you are a computing scientist). I will mention a few of them.
-
Every type of binary operation defined by equations corresponds to a monad. But some of them are unsolvable, meaning you cannot describe the monad precisely.
There will probably be long delay before I get back to this project. There are too many other things I want to do!
