Monoid homomorphisms

Because many operations and data structures are monoids, it is interesting to use the associated concepts as the computational building block of an essential calculus. In particular, iteration over collection types can be elegantly formulated as computing a monoid homomorphism. This notion coincides with the usual mathematical notion of homomorphism, albeit given here from an operational standpoint and biased toward collection monoids. Basically, a monoid homomorphism $\ensuremath{\mathfrak{hom}}_{\oplus}^{\odot}$ maps a function $f$ from a collection monoid $\oplus$ to any monoid $\odot$ by collecting all the $f$-images of elements of a $\oplus$-collection using the $\odot$ operation. For example, the expression $\ensuremath{\ensuremath{\mathfrak{hom}}_{\ensuremath{\!+\!\!+}}^{\cup}}[\lambda x.x+1]$ applied to the list $[1,2,1,3,2]$ returns the set $\{2,3,4\}$. In other words, the monoid homomorphism $\ensuremath{\mathfrak{hom}}_{\ensuremath{\!+\!\!+}}^{\cup}$ of a function $f$ applied to a list $L$ corresponds to the following loop computation:

$$\begin{array}{ll} \t{result}\;\leftarrow\;\{\}; \\ \b{fore... ...t{result}\cup f(x); \\ \b{return}\;\; \t{result}; \end{array}$$

This is formulated formally as follows:

DEFINITION 4.1 (Monoid Homomorphism)   A Monoid Homomorphism $\ensuremath{\mathfrak{hom}}_{\oplus}^{\odot}$ defines a mapping from a collection homomorphism $\oplus$ to any monoid $\odot$ such that $\Theta_{\oplus}\subseteq\Theta_{\odot}$ by:

$$\renewedcommand{arraystretch}{1.6}\begin{array}{l@{\;\;\ensu... ...\ensuremath{\mathfrak{hom}}_{\oplus}^{\odot}}[f](y) \end{array}$$

for any function $f:\alpha\rightarrow \ensuremath{\mathfrak{T}}_{\odot}$, $x:\alpha$, and $y:\alpha$, where $\ensuremath{\mathfrak{T}}_{\oplus}=\ensuremath{\mathfrak{C}}_{\oplus}(\alpha)$.

Again, computationally, this amounts to executing the following iteration:

$$\begin{array}{ll} \t{result}\;\leftarrow\;\ensuremath{\mathfr... ...result}\odot f(x_i); \ \b{return}\;\; \t{result}; \end{array}$$ (1)

The reader may be puzzled by the condition $\Theta_{\oplus}\subseteq\Theta_{\odot}$ in Definition 4.1. It means that a monoid homomorphisms may only be defined from a collection monoid to a monoid that has at least the same equational theory. In other words, one can only go from an empty theory monoid, to either a $\{C\}$-monoid or an $\{I\}$-monoid, or yet to a $\{C,I\}$-monoid. This requirement is due to an algebraic technicality, and relaxing it would enable a monoid homomorphism to be ill-defined. To see this, consider going from, say, a commutative-idempotent monoid to one that is commutative but not idempotent. Let us take, for example, $\ensuremath{\mathfrak{hom}}_{\cup}^{+}$. Then, this entails:

$$\renewedcommand{arraystretch}{1.6}\begin{array}{l@{\;=\;}l} ... ...}^{+}}[\lambda x.1](\{a\}) \\ & 1 + 1 \\ & 2. \end{array}$$

The reader may have noticed that this restriction has the unfortunate consequence of disallowing potentially useful computations, notable examples being computing the cardinality of a set, or converting a set into a list. However, this drawback can be easily overcome with a suitable modification of the third clause in Definition 4.1, and other expressions based on it, ensuring that anomalous cases such as the above are dealt with by appropriate tests.

Also of importance for the consistency of Definition 4.1 is the fact that a non-idempotent monoid must be anti-idempotent, and a non-commutative monoid must be anti-commutative. Indeed, if $\oplus$ is non-idempotent as well as non-anti-idempotent (say, $x_0\oplus x_0=x_0$ for some $x_0$), then this entails:

$$\renewedcommand{arraystretch}{1.6}\begin{array}{l@{\;=\;}l} ... ...nsuremath{\mathfrak{hom}}_{\oplus}^{\odot}}[f](x_0) \end{array}$$

which is not necessarily true for non-idempotent $\odot$. A similar argument may be given for commutativity. This consistency condition is in fact not restrictive operationally as it is always verified (e.g., a list will not allow partial commutation of any of its element).

Here are a few familar functions expressed with well-defined monoid homomorphisms:

$$\renewedcommand{arraystretch}{1.6}\begin{array}{l@{\;=\;}l} ... ...n}}\;\{x\}\;\ensuremath{\mathfrak{else}}\;\{\}](s). \end{array}$$