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

a binary operation from pairs of elements of into such that for all

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

traitMonoid[A] { defmempty: A defmappend(a: A, b: A): A }

mappend is the binary operation , and mempty is the element .

More concretely, we wrote this:

1 2 3 4

objectIntMonoidextendsMonoid[Int] { defmempty: Int = 0 defmappend(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

and

.

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

@ traitMonoid[A] { defmempty: A defmappend(a: A, b: A): A } defined traitMonoid

@ objectMonoid{ implicitobjectStringMonoidextendsMonoid[String] { defmempty: String = "" defmappend(a: String, b: String): String = a + b } implicitobjectIntMonoidextendsMonoid[Int] { defmempty: Int = 0 defmappend(a: Int, b: Int) = a + b } } defined objectMonoid

Next, we’ll write a homomorphism

1 2

@ deff(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 @ importMonoid._ importMonoid._

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.