Monoid

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

  1. 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$
  2. 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
2
3
4
trait Monoid[A] {
  def mempty: A
  def mappend(a: A, b: A): A
}

mappend is the binary operation $\bullet$, and mempty is the element $e$.

More concretely, we wrote this:

1
2
3
4
object IntMonoid extends Monoid[Int] {
  def mempty: Int = 0
  def mappend(a: Int, b: Int) = a + b
}

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

  1. $f(e) = e^\prime$ and
  2. $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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@ trait Monoid[A] {
    def mempty: A
    def mappend(a: A, b: A): A
  }
defined trait Monoid

@ object Monoid {
    implicit object StringMonoid extends Monoid[String] {
        def mempty: String = ""
        def mappend(a: String, b: String): String = a + b
    }
    implicit object IntMonoid extends Monoid[Int] {
        def mempty: Int = 0
        def mappend(a: Int, b: Int) = a + b
    }
  }
defined object Monoid

Next, we’ll write a homomorphism $f: M \rightarrow M^\prime$

1
2
@ def f(s: String): Int = s length
defined function f

Let’s see this in action. We’ll begin by testing the first rule.

1
2
3
4
5
6
7
// bring the monoids into scope
@ import Monoid._
import Monoid._

// rule 1
@ f(StringMonoid.mempty) == IntMonoid.mempty
res6: Boolean = true

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
2
3
4
5
6
7
8
@ val x = "apple"
x: String = "apple"
@ val y = "banana"
y: String = "banana"

// rule 2
@ f( StringMonoid.mappend(x, y) ) == IntMonoid.mappend( f(x), f(y) )
res9: Boolean = true

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.