Monadic Units

There is an aspect of monads that I did not get into in my previous post on monads: the unit. What I described in there at the end was slightly less than a monoid: it was a semigroup, which is to say, a monoid which may or may not have a unit.

Semigroups, monoids and units

The most widely used instances of monoids are numbers (naturals, integers, rationals, reals or complex numbers) together with the addition operation in which the unit is 0, and numbers together with the multiplication operation in which the unit is 1.

The defining binary operator with type signature \(M\times M\to M\) (addition or multiplication in the case of numbers) for a monoid must be associative. Remember that the defining operator is binary, and therefore, applying these operators on lists longer than 2 requires making choices of parenthesizations. The associativity constraint \[ a \circ (b \circ c) = (a\circ b)\circ c \] makes application of such reduction operators on addition or multiplication together with a list easier to implement as we do not have to worry about the choices we have to make.

In order to go further with more elaborate examples on units, we must think of these elements as unary operators of left and right variants whose type signatures are \(M\to M\times M\) which is exactly the opposite of the type signature of our binary operator. In the case of addition operator:

add-left-unit(x) = (x,0)

add-right-unit(x) = (0,x)

Now, if we apply addition to the resulting pair we get back the element we started with. There is a similar version of this for multiplication.

Let me implement these in lisp to demonstrate how it works.

(defun add-left-unit (x) (list 0 x))

(defun add-right-unit (x) (list x 0))

(defvar num (random 10))
num
6

(reduce '+ (add-left-unit num))
6

(reduce '+ (add-right-unit num))
6

The monad (vectorize,flatten)

Going back to monads, let me recall the functions vectorize and flatten from my previous post on monads:

(defun vectorize (f) (lambda (x) (mapcar f x)))

(defun flatten (x)
   (cond ((null x) nil)
         ((atom x) (list x))
         (t (mapcan 'flatten x))))

In this case vectorize together with flatten forms a monad, i.e. a monoid in the category of endofunctors. The binary operator of addition or multiplication is replaced with flatten whose type signature is flatten::[[a]] -> [a]. This means if we have a unit, its type signature must be unit:: [a] -> [[a]]. This also means that I will have be more careful in implementing flatten and I will redefine it as follows:

(defun flatten (x)
   (loop for i in x append i))

(flatten '((0 1) (2 3 4) ((5 6)) (7 8) (9)))
(0 1 2 3 4 (5 6) 7 8 9)

Given a list \(L\) of objects of type \(A\), there are two ways one can create a list of list of objects of type \(A\):

1. Either create a new list which contains a single element \(L\).
2. Or for each \(x\) in \(L\) create a list containing just \(x\) and combine the results into a new list.

In lisp one possible implementation of these left and right units can be accomplished as follows:

(defun flatten-right-unit (x) (list x))

(defun flatten-left-unit (x) (funcall (vectorize 'list) x))

Let me test these functions against flatten:

(defvar my-list (loop for i from 1 to 10 collect (random 10)))
my-list
(3 0 7 4 1 7 5 1 8 5)

(flatten (flatten-right-unit my-list))
(3 0 7 4 1 7 5 1 8 5)

(flatten (flatten-left-unit my-list))
(3 0 7 4 1 7 5 1 8 5)

In other words, flatten has a unit, which means, the pair (vectorize,flatten) is really a monad instead of being a semigroup object in the category of endofunctors.