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 is an underlying equipped with

  1. a binary operation from pairs of elements of into such that for all
  2. an element such that

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 , and mempty is the element .

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, translates to the addition operation , and translates to . That way, where is any integer. That was fairly easy to understand.

Monoid Homomorphism

A monoid homomorphism from to is a function such that

  1. and
  2. .

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 

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 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, is a homomorphism such that . 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 , which is the zero/identity element of IntMonoid.

Category with One Object

Suppose there’s a category with just one object in it. The identity arrow would point to itself. And the composition of this arrow with itself is , which satisfies the associativity law. A monoid 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 is represented as the identity arrow, and the operation is represented as composition of arrows.

Any category with a single object is a monoid.