# Part II: Free Monoids

## String Diagrams

The utility of diagrams in formulating and proving theorems in category theory cannot be overemphasized. While working my way through the construction of free monoids, I noticed that there was a particular set of manipulations that had to be done algebraically, with little help from diagrams. These were operations involving a mix of tensor products and composition of morphisms. Tensor product is a bifunctor, so it preserves composition; which means you can often slide products through junctions of arrows—but the rules are not immediately obvious. Diagrams in which objects are nodes and morphisms are arrows have no immediate graphical representation for tensor products. A thought occurred to me that maybe a dual representation, where morphisms are nodes and objects are edges would be more accommodating. And indeed, a quick search for “string diagrams in monoidal categories” produced a paper by Joyal and Street, “The geometry of tensor calculus.”

The idea is very simple: if you represent morphisms as points on a plane, you have two additional dimensions to play with composition and tensoring. Two morphism—represented as points—can be composed if they share an object, which can be represented as a line connecting them. By convention, we read composition from the bottom of the diagram up. We follow lines as they go through points—that’s composition. Two lines ascending in parallel represent a tensor product. The geometry of the diagram just works!

Let me explain it on a simple example—the left unit law for a monoid :

The left hand side is a composition of two morphisms. The first morphism starts from the object (see Fig. 12).

In principle, there should be two parallel lines at the bottom, one for and one for ; but is isomorphic to , so the line is redundant and can be omitted. Scanning the diagram from the bottom up, we encounter the morphism in parallel with the line. That’s exactly the graphical representation of . The output of is also , so we now have two upward moving lines, corresponding to . That’s the input of the next morphism . Its output is the single upward moving . The unit law may be visualized as pulling the two strings in opposite direction until the whole diagram is straightened to one vertical string corresponding to .

Here’s the right unit law:

It works like a mirror image of the left unit law:

The associativity law can be illustrated by the following diagram:

The important property of a string diagram is that, because of functoriality, its value—the compound morphism it represents—doesn’t change under continuous transformations.

## Monoid

First we’d like to show that the carrier of the free -algebra which, as we’ve seen before, is also the initial algebra for the list functor , is automatically a monoid. To show that, we need to define its unit and multiplication—two morphisms that satisfy monoid laws. The obvious candidate for unit is the universal mapping . It’s the morphism in the definition of the free algebra from the previous post (see Fig 15).

Multiplication is a morphism:

which, if you think of a free monoid as a list, is the generalization of list concatenation.

The trick is to show that is also a free -algebra whose generator is itself. We could then use the universality of to generate the unique algebra morphism from it to (which is also an -algebra). That will be our .

*Proposition*. {Monoid.}

The free -algebra generated by the unit object is a monoid whose unit is:

and whose multiplication:

is the unique -algebra morphism

induced by the identity morphism .

*Proof*.

In the previous post we’ve shown that, if is a free algebra generated by the unit object with the universal map , then is a free algebra generated by with the universal map (see Fig. 16).

We get by redrawing this diagram: using as both the generator and the target algebra, and replacing with (see Fig. 17):

Since so defined is an -algebra morphism, it makes the following diagram, Fig. 18, commute.

This commuting condition can be redrawn as the identity of two string diagrams (Fig. 19) corresponding to the two paths through the original diagram.

The universal condition in Fig. 17:

gives us immediately the left unit law for the monoid.

The right unit law:

requires a little more work.

There is a standard trick that we can use to show that two morphisms, whose source (in this case ) is a free algebra, are equal. It’s enough to prove that they are algebra morphisms, and that they are both induced by the same morphism (in this case ). Their equality then follows from the uniqueness of the universal construction.

We know that is an algebra morphism so, if we can show that is also an algebra morphism, their composition will be an algebra morphism too. Trivially, is an algebra morphism so, if we can show that the two are induced by the same regular morphism , then they must be equal.

To show that is an -algebra morphism, we have to show that the diagram in Fig. 20 commutes.

We can redraw the two paths through Fig. 20 as two string diagrams in Fig. 21. They are equal because they can be deformed into each other.

Therefore the composition is also an -algebra morphism. The string diagram that illustrates this fact is shown in Fig. 22.

Since the identity -algebra morphism is induced by , we’d like to show that is also induced by (Fig. 23).

To do that, we have to prove the universal condition in Fig. 23:

This is represented as a string diagram identity in Fig. 24. We can deform this diagram by sliding the left node up, past the right node, and then using the left identity.

This concludes the proof of the right identity.

The proof of associativity is very similar, so I’ll just sketch it. We have to show that the two diagrams in Fig. 14 are equal. We’ll use the same trick as before. We’ll show that they are both algebra morphisms. Their source is a free algebra generated by (see Fig. 25—the other diagram has replaced by ). The universal condition follows from the unit law for . Associativity condition:

will then follow from the uniqueness of the universal construction.

You can easily convince yourself that showing that something is an -algebra morphism can be done by first attaching the leg to the left of the string diagram and then sliding it to the top of the diagram, as illustrated in Fig. 26. This can be accomplished by repeatedly using the fact that is an -algebra morphism.

The same process can be applied to the second associativity diagram, thus completing the proof.

For Haskell programmers, recall from the previous post our construction of the free -algebra generated by and the derivation of the algebra morphism from it to the internal-hom algebra:

g :: Expr -> (k -> n) g () = f g a = k -> nu (a, f k) g (a, b) = k -> nu (a, nu (b, f k)) ...

In the current proof we have replaced with , which generalizes the list of s, became , and is a function that prepends an element to a list. In other words, concatenates its list-argument in front of the second list, and it does it in the correct order.

## Free Monoid

The monoid whe have just constructed from the free algebra is a free monoid. As we did with free algebras, instead of using the free/forgetful adjunction to prove it, we’ll use the free-object universal construction.

*Theorem*. {Free Monoid.}

The monoid is a *free* monoid generated by , with a universal mapping given by :

That is, for any monoid and any morphism , there is a unique *monoid morphism* from to such that the universal condition holds:

(see Fig. 27).

*Proof*. Recall that is a free -algebra generated by . It turns out that any monoid , for which there is a morphism , is automatically a carrier of an -algebra. We construct its structure map by combining with monoid multiplication :

We can use ‘s monoidal unit to insert into . Because is a free -algebra, there is a unique algebra morphism, let’s call it , from it to , which is induced by , such that (see Fig. 28). We want to show that this algebra morphism is also a *monoid morphism*. Furthermore, if we can show that this is the *unique* monoid morphism induced by , we will have a proof that is a free monoid.

Since is an algebra morphism, the rectangle in Fig. 29 commutes.

Let’s redraw it as an identity of string diagrams, Fig. 30. We’ll make use of it in a moment.

Going back to Fig. 27, we want to show that the universal condition holds, which means that we want the diagram in Fig. 31 to commute (I have expanded the definition of ).

In other words we want show that the following two string diagrams are equal:

Using the identity in Fig. 30, the left hand side can be rewritten as:

The right leg can be shrunk down to using the universal condition in Fig. 28:

which, incidentally, also expresses the fact that preserves the monoidal unit.

Finally, we can use the right unit law for the monoid , Fig. 34,

to arrive at the right hand side of the identity in Fig. 32. This completes the proof of the universal condition in Fig. 27.

Now we have to show that is a full-blown monoid morphism, that is, it preserves multiplication (Fig. 35).

The corresponding string diagrams are shown in Fig. 36.

Let’s start with the fact that is the free -algebra generated by . We will show that the two paths through the diagram in Fig. 35 are both -algebra morphisms, and that they are induced by the same regular morphism . Therefore they must be equal.

The bottom path in Fig. 35, , is an -algebra morphism by virtue of being a composition of two -algebra morphisms. This composite is induced by morphism in the diagram Fig. 37.

The universal condition in Fig. 37 follows from the diagram in Fig. 38, which follows from the left unit law for the monoid .

We want to show that the top path in Fig. 35 is also an -algebra morphism, that is, the diagram in Fig. 39 commutes.

We can redraw this diagram as a string diagram identity in Fig. 40.

First, let’s use the associativity law for the monoid to transform the left hand side. We get the diagram in Fig. 41.

We can now apply the identity in Fig. 30 to reproduce the right hand side of Fig. 40.

We have thus shown that both paths in Fig. 35 are algebra morphisms. We know that the bottom path is induced by morphism . What remains is to show that the top path, which is given by is induced by the same . This will be true, if we can show the universal condition in Fig. 42.

This universal condition can be expanded to the diagram in Fig. 43.

Here’s the string diagram that traces the path around the square (Fig. 44).

First, let’s use the preservation of unit by , Fig. 45, to shrink the left leg,

and follow it with the left unit law for the monoid (Fig. 46). The result is that Fig. 44 shrinks to the single morphism , thus making Fig. 43 commute.

This completes the proof that is a monoid morphism.

The final step is to make sure that is the *unique* monoid morphism from to . Suppose that there is another monoid morphism (replacing in Fig. 28). If we can show that is also an -algebra morphism induced by the same , it will have to, by universality, be equal to . In other words, we have to show that the diagram in Fig. 28 also works for . Our assumptions are that both and are monoid morphisms, that is, they preserve unit and multiplication; and they both satisfy the universal condition in Fig 27. In particular, satisfies the condition in Fig. 47.

Notice that, in the first part of the proof, we started with an -algebra morphism and had to show that it’s a monoid morphism. Now we are going in the opposite direction: we know that is a monoid morphism, and have to show that it’s an -algebra morphism, and that the universal condition in Fig. 28

holds. The latter simply restates our assumption that preserves the unit.

To show that is an algebra morphism, we have to show that the diagram in Fig 48 commutes.

This diagram may be redrawn as a pair of string diagrams, Fig 49.

The proof of this identity relies on redrawing string diagrams using the identities in Figs. 12, 19, 36, and 47. Before we continue, you might want to try it yourself. It’s an exercise well worth the effort.

We start by expanding the node using the diagram in Fig. 47 to get Fig. 50.

We can now use the preservation of multiplication by to obtain Fig 51.

Next, we can use the fact that is an -algebra morphism, Fig. 19, to slide the node up, and obtain Fig. 52.

We can now use the left unit law for the monoid :

as illustrated in Fig. 12, to arrive at the right hand side of Fig. 49.

This concludes the proof that must be equal to .

## Conclusion

To summarize, we have shown that the free monoid can be constructed from a free algebra of the functor . This is a very general result that is valid in any monoidal closed category. Earlier we’ve seen that this free algebra is also the initial algebra of the list functor . The immediate consequence of this theorem is that it lets us construct free monoids in functor categories with interesting monoidal structures. In particular, we get a free monad as a free monoid in the category of endofunctors with functor composition as tensor product. We can also get a free applicative, or free lax monoidal functor, if we define the tensor product as Day convolution—the latter can be also constructed in the profunctor category.

## Leave a Reply