Monoids

In this section, all notions and notations relating to monoids as they are used in this paper are recalled and justified.

Mathematically, a monoid is a non-empty set equipped with an associative internal binary operation and an identity element for this operation. Formally, let $S$ be a set, $\star$ a function from $S\times S$ to $S$, and $\epsilon\in S$; then, $\langle S,\star,\epsilon\rangle$ is a monoid iff, for any $x, y, z$ in $S$:

$$x\star(y\star z) = (x\star y)\star z$$ (3)

and

$$x\star\epsilon = \epsilon\star x = \epsilon.$$ (4)

Most familiar mathematical binary operations define monoids. For example, taking the set of natural numbers $\ensuremath{\mathbb{N}}$, and the set of boolean values $\ensuremath{\mathbb{B}}=\{\ensuremath{\mathfrak{true}},\ensuremath{\mathfrak{false}}\}$, the following are monoids:

• $\langle \ensuremath{\mathbb{N}},+,0\rangle$,
• $\langle \ensuremath{\mathbb{N}},*,1\rangle$,
• $\langle \ensuremath{\mathbb{N}},\max,0\rangle$,
• $\langle \ensuremath{\mathbb{B}},\vee,\ensuremath{\mathfrak{false}}\rangle$,
• $\langle \ensuremath{\mathbb{B}},\wedge,\ensuremath{\mathfrak{true}}\rangle$.

The operations of these monoids are so familiar that they need not be explicated. For us, they have a ``built -in'' semantics that allows us to compute with them since primary school. Indeed, we shall refer to such readily interpreted monoids as primitive monoids.³

Note that the definition of a monoid does not preclude additional algebraic structure. Such structure may be specified by other equations augmenting the basic monoid equational theory given by the conjunction of equations (3) and  (4). For example, all five monoids listed above are commutative; namely, they also obey equation (5):

$$x\star y = y\star x$$ (5)

for any $x, y$. In addition, the three last ones (i.e., $\max$, $\vee$, and $\wedge$) are also idempotent; namely, they also obey equation (6):

$$x\star x = x$$ (6)

for any $x$.

Not all monoids are primitive monoids. That is, one may define a monoid purely syntactically whose operation only builds a syntactic structure rather than being interpreted using some semantic computation. For example, linear lists have such a structure: the operation is list concatenation and builds a list out of two lists; its identity element is the empty list. A syntactic monoid may also have additional algebraic structure. For example, the monoid of bags is also defined as a commutative syntactic monoid with the disjunct union operation and the empty bag as identity. Or, the monoid of sets is a commutative and idempotent syntactic monoid with the union operation and the empty set as identity.

Because they are not interpreted, syntactic monoids pose a problem as far as representation of its elements is concerned. To illustrate this, let us consider an empty-theory algebraic structure; that is, one without any equations--not even associativity nor identity. Let us take such a structure with one binary operation $\star$ on, say, the natural numbers $\ensuremath{\mathbb{N}}$. Saying that $\star$ is a ``syntactic'' operation means that it constructs a syntactic term (i.e., an expression tree) by composing two other syntactic terms. We thus can define the set $T_{\star}$ of $\star$-terms on some base set, say the natural numbers, inductively as the limit $\cup_{n\geq 0}T_n$ where,

$$T_n \;\ensuremath{\;\stackrel{\mbox{\tiny def}}{=}\;}\; \left\{ \... ... t_2 \;\vert\; t_i\in T_{n-1}, i=1,2 \} & \makebox{if $n>0$} \end{array}\right.$$ (7)

Clearly, the set $T_{\star}$ is well defined and so is the $\star$ operation over it. Indeed, $\star$ is a bona fide function from $T_{\star}\times T_{\star}$ to $T_{\star}$ mapping two terms $t_1$ and $t_2$ in $T_{\star}$ into a unique term in $T_{\star}$--namely, $t_1\star t_2$. This is why $T_{\star}$ is called the syntactic algebra.⁴

Let us now assume that the $\star$ operation is associative--i.e., that $\star$-terms verify Equation (3). Note that this equation defines a (syntactic) congruence on $T_{\star}$ which identifies terms such as, say, $1\star(2\star3)$ and $(1\star2)\star3$. In fact, for such an associative $\star$ operation, the set $T_{\star}$ defined in Equation (7) is not the appropriate domain. Rather, the right domain is the quotient set whose elements are (syntactic) congruence classes modulo associativity of $\star$. Therefore, this creates an ambiguity of representation of the syntactic structures.⁵

Similarly, more algebraic structure defined by larger equational theories induces coarser quotients of the empty-theory algebra by putting together in common congruence classes all the syntactic expressions that can be identified modulo the theory's equations. The more equations, the more ambiguous the syntactic structures of expressions. Mathematically, this poses no problem as one can always abstract away from individuals to congruence classes. However, operationally one must resort to some concrete artifact to obtain a unique representation for all members of the same congruence class. One way is to devise a canonical representation into which to transform all terms. For example, an associative operation could systematically ``move'' nested subtrees from its left argument to its right argument--in effect using Equation (3) as a one-way rewrite rule. However, while this is possible for some equational theories, it is not so in general--e.g., take commutativity.⁶

From a programming standpoint (which is ours), we can abstract away from the ambiguity of canonical representations of syntactic monoid terms using a flat notation. For example, in LISP and Prolog, a list is seen as the (flat) sequence of its constituents. Typically, a programmer writes $[1,2,1]$ to represent the list whose elements are $1$, $2$ and $1$ in this order, and does not care (nor need s/he be aware) of its concrete representation. A set--i.e., a commutative idempotent syntactic monoid--is usually denoted by the usual mathematical notation $\{1,2\}$, implicitly relying on disallowing duplicate elements, not minding the order in which the elements appear. A bag, or multiset--i.e., a commutative but non-idempotent syntactic monoid--uses a similar notation, allowing duplicate elements but paying no heed to the order in wich they appear; i.e., $\{\!\!\{1,2,1\}\!\!\}$ is the bag containing $1$ twice, and $2$ once.

Syntactic monoids are quite useful for programming as they provide adquate data structures to represent collections of objects of a given type. Thus, we refer to them as collection monoids. Now, a definition such as Equation (7) for a syntactic monoid, although sound mathematically, is not quite adequate for programming purposes. This is because it defines the $\star$ operations on two distinct types of elements; namely, the base elements (here natural numbers) and constructed elements. In programming, it is desirable that operations be given a crisp type. A way to achieve this is by systematically ``wrapping'' each base element $x$ into a term such as $x\star\epsilon$. This ``wrapping'' is achieve by associating to the monoid a function $\ensuremath{\mathfrak{u}}_{\star}$ from the base set into the monoid domain called its unit injection. For example, if $\ensuremath{\!+\!\!+}$ is the list monoid operation for concatenating two lists, $\ensuremath{\mathfrak{u}}_{\ensuremath{\!+\!\!+}}(x)=[x]$ and one may view the list $[a,b,c]$ as $[a]\ensuremath{\!+\!\!+}[b]\ensuremath{\!+\!\!+}[c]$. Similarly, the set $\{a,b,c\}$ is viewed as $\{a\}\cup\{b\}\cup\{c\}$, and the bag $\{\!\!\{a,b,c\}\!\!\}$ as $\{\!\!\{a\}\!\!\}\uplus\{\!\!\{b\}\!\!\}\uplus\{\!\!\{c\}\!\!\}$. Clearly, this bases the constructions on an isomorphic view of the base set rather than the base set itself, while using a uniform type for the monoid operator. Also, because the type of the base elements is irrelevant for the construction other than imposing the constraint that all such elements be of the same type, we present a collection monoid as a polymorphic data type. This justifies the formal view of monoids we give next using the programming notion of type.

Because it is characterized by its operation $\oplus$, a monoid is often simply referred to as $\oplus$. Thus, a monoid operation is used as a subscript to denote its characteristic attributes. Namely, for a monoid $\oplus$,

• $\ensuremath{\mathfrak{T}}_{\oplus}$ is its type (i.e., $\oplus: \ensuremath{\mathfrak{T}}_{\oplus}\times\ensuremath{\mathfrak{T}}_{\oplus}\rightarrow \ensuremath{\mathfrak{T}}_{\oplus}$),

• $\ensuremath{\mathfrak{z}}_{\oplus} : \ensuremath{\mathfrak{T}}_{\oplus}$ is its identity element,

• $\Theta_{\oplus}$ is its equational theory (i.e., a subset of the set $\{C,I\}$, where $C$ stands for ``commutative'' and $I$ for ``idempotent'');

and, if it is a collection monoid,

• $\ensuremath{\mathfrak{C}}_{\oplus}$ is its type constructor (i.e., $\ensuremath{\mathfrak{T}}_{\oplus}=\ensuremath{\mathfrak{C}}_{\oplus}(\alpha)$),

• $\ensuremath{\mathfrak{u}}_{\oplus} : \alpha\rightarrow \ensuremath{\mathfrak{C}}_{\oplus}(\alpha)$ is its unit injection.

Table 1 summarizes the monoid attributes of a few usual monoids.

Table 1: Attributes of a few common monoids

$\oplus$	$\ensuremath{\mathfrak{T}}_{\oplus}$	$\ensuremath{\mathfrak{z}}_{\oplus}$	$\Theta_{\oplus}$
$+$	$\mathtt{int}$	0	$\{C\}$
$*$	$\mathtt{int}$	$1$	$\{C\}$
$\max$	$\mathtt{int}$	0	$\{C,I\}$
$\vee$	$\mathtt{bool}$	$\ensuremath{\mathfrak{false}}$	$\{C,I\}$
$\wedge$	$\mathtt{bool}$	$\ensuremath{\mathfrak{true}}$	$\{C,I\}$

$\oplus$	$\ensuremath{\mathfrak{C}}_{\oplus}$	$\ensuremath{\mathfrak{T}}_{\oplus}$	$\ensuremath{\mathfrak{z}}_{\oplus}$	$\ensuremath{\mathfrak{u}}_{\oplus}(x)$	$\Theta_{\oplus}$
$\cup$	$\ensuremath{\mathtt{set}}$	$\ensuremath{\mathtt{set}}(\alpha)$	$\{\}$	$\{x\}$	$\{C,I\}$
$\uplus$	$\ensuremath{\mathtt{bag}}$	$\ensuremath{\mathtt{bag}}(\alpha)$	$\{\!\!\{\}\!\!\}$	$\{\!\!\{x\}\!\!\}$	$\{C\}$
$\ensuremath{\!+\!\!+}$	$\ensuremath{\mathtt{list}}$	$\ensuremath{\mathtt{list}}(\alpha)$	$[]$	$[x]$	$\emptyset$

Primitive monoids

Collection monoids