Monoid comprehensions

The concept of monoid homomorphism is useful for expressing a formal semantics of iteration over collections. However, it is not very convenient as a programming construct. A natural notation for such a construct that is both conspicuous and can be expressed in terms of monoid homomorphisms is a monoid comprehension. This notion generalizes the familiar notation used for writing a set in comprehension (as opposed to writing it in extension) using a pattern and a formula describing its elements (as oppposed to listing all its elements). For example, the set comprehension $\{\langle x,x^2\rangle \;\vert\;x\in\ensuremath{\mathbb{N}}, \exists n.x=2n\}$ describes the set of pairs $\langle x,x^2\rangle$ (the pattern), verifying the formula $x\in\ensuremath{\mathbb{N}}, \exists n.x=2n$ (the qualifier).

This notation can be extended to any (primitive or collection) monoid $\oplus$. The syntax of a monoid comprehension is an expression of the form $\oplus\{e\;[\!]\;Q\}$ where $e$ is an expression called the head of the comprehension, and $Q$ is called its qualifier and is a sequence $q_1,\ldots,q_n$, $n\geq0$, where each $q_i$ is either

• a generator of the form $x\;\leftarrow\;e$, where $x$ is a variable and $e$ is an expression; or,

• a filter $\phi$ which is a boolean condition.

In a monoid comprehension expression $\oplus\{e\;[\!]\;Q\}$, the monoid operation $\oplus$ is called the accumulator.

As for semantics, the meaning of a monoid comprehension is defined in terms of monoid homomorphisms.

DEFINITION 4.2 (Monoid Comprehension)   The meaning of a monoid comprehension over a monoid $\oplus$ is defined inductively as follows:

$$\renewedcommand{arraystretch}{1.6}\begin{array}{l@{\;\ensurem... ...mathfrak{else}}\;\ensuremath{\mathfrak{z}}_{\oplus} \end{array}$$

such that $e:\ensuremath{\mathfrak{T}}_{\oplus}$, $e':\ensuremath{\mathfrak{T}}_{\odot}$, and $\odot$ is a collection monoid.

Note that although the input monoid $\oplus$ is explicit, each generator $x\;\leftarrow\;e'$ in the qualifier has an implicit collection monoid $\odot$ whose characteristics can be inferred with polymorphic typing rules.

Although Definition 4.2 can be effectively computed using nested loops (i.e., using the iteration semantics (1)), such would be in general rather inefficient. Rather, an optimized implementation can be achieved by various syntactic transformation expressed as rewrite rules. Thus, the principal benefit of using monoid comprehensions is to formulate efficient optimizations on a simple and uniform general syntax of expressions irrespective of specific monoids.

Note that relational joins are immediately expressible as monoid comprehensions. Indeed, the join of two sets $S$ and $T$ using a function $f$ and a predicate $p$ is simply:

$$S \vartriangleright\!\!\vartriangleleft _p^f T \;\ensuremath{\;\s... ... \ensuremath{\cup\{f(x,y)\;[\!]\;x\;\leftarrow\;S, y\;\leftarrow\;T, p(x,y)\}}.$$ (2)

Typically, a relational join will take $f$ to be a record constructor. For example, if we write a record whose fields $\t{l}_i$ have values $e_i$ for $i=1,\ldots,n$, as $\langle \t{l}_1=e_1,,\ldots,\t{l}_n=e_n\rangle$, then a standard relational join is obtained with, say, $f(x,y) = \langle \t{name}=y.\t{name},\t{age}=2*x.\t{age}\rangle$, and $p(x,y)$ may be any condition such as $x.\t{name}=y.\t{name}, x.\t{age}\geq 18$.

Clearly, monoid comprehensions can immediately express queries using all usual relational operators (and, indeed, object queries as well) and most usual functions. For example,

$$\begin{array}{l@{\hskip2em}l} \renewedcommand{arraystretch}{... ...\;\leftarrow\;s, x\;\leftarrow\;t\}}\\ \end{array}\end{array}$$

Note that some of these functions will work only on appropriate types of their arguments. For example, the type of the argument of $\t{sum}$ must be a non-idempotent monoid, and so must the type of the second argument of tex2html_wrap_inlinecount. Thus, tex2html_wrap_inlinesum will add up the elements of a bag or a list, and tex2html_wrap_inlinecount will tally the number of occurrences of an element in a bag or a list. Applying either tex2html_wrap_inlinesum or tex2html_wrap_inlinecount to a set will be caught as a type error.