The first algebraic structure we’ll look at is a monoid. We’ve covered monoid previously in Scalaz Under the Hoods. In this post we’ll look at it again from a more abstract standpoint.
Formal Definition
A monoid $(M, \bullet, e)$ is an underlying $M$ equipped with
- a binary operation $\bullet$ from pairs of elements of $M$ into $M$ such that $(x \bullet y) \bullet z = x \bullet (y \bullet z)$ for all $x, y, z \in M$
- an element $e$ such that $e \bullet x = x = x \bullet e$
We’ve already translated this definition to code. Just to recap, here’s what we wrote previously:
1 | trait Monoid[A] { |
mappend
is the binary operation $\bullet$, and mempty
is the element $e$.
More concretely, we wrote this:
1 | object IntMonoid extends Monoid[Int] { |
So, $\bullet$ translates to the addition operation $+$, and $e$ translates to $0$. That way, $0 + x = x = x + 0$ where $x$ is any integer. That was fairly easy to understand.
Monoid Homomorphism
A monoid homomorphism from $(M, \bullet, e)$ to $(M^\prime, \bullet^\prime, e^\prime)$ is a function $f: M \rightarrow M^\prime$ such that
- $f(e) = e^\prime$ and
- $f(x \bullet y) = f(x) \bullet^\prime f(y)$.
The composition of two monoid homomorphisms is the same as their composition as functions on sets.
I know this is abstract so let’s have a look at a concrete example. Let’s write some code. We’ll be reusing the monoids that we previously wrote.
1 | @ trait Monoid[A] { |
Next, we’ll write a homomorphism $f: M \rightarrow M^\prime$
1 | @ def f(s: String): Int = s length |
Let’s see this in action. We’ll begin by testing the first rule.
1 | // bring the monoids into scope |
So we see that the first rule is satisfied. Applying $f$ on the zero element of StringMonoid
gives us the zero element of IntMonoid
. Onto the second rule.
1 | @ val x = "apple" |
And we see that the second rule is also satisfied. Therefore, $f$ is a homomorphism such that $f: StringMonoid \rightarrow IntMonoid$. To recap, a monoid homomorphism is a map between monoids that preserves the monoid operation and maps the identity element of the first monoid to that of the second monoid[1]. The monoid operation is still $+$ and the empty string is mapped to $0$, which is the zero/identity element of IntMonoid
.
Category with One Object
Suppose there’s a category $A$ with just one object in it. The identity arrow $id_A$ would point to itself. And the composition of this arrow with itself is $id_A$, which satisfies the associativity law. A monoid $(M, \bullet, e)$ may be represented as a category with a single object. The elements of M are represented as arrows from this object to itself, the identity element $e$ is represented as the identity arrow, and the operation $\bullet$ is represented as composition of arrows.
Any category with a single object is a monoid.