/ Cats/Scala

What is a Monoid?

We often need to combine data types that may be "empty" e.g. empty Lists or Options. How do we combine a Seq[Int] to produce an Int if the Seq is empty? What is the result? How about Seq[String] => String. Logically we would expect zero for the Int example and "" for the String but how do we represent this?

TL;DR The simple Monoid extends Semigroup and adds a default or fallback value for the given type. It allows us to combine empty data types so long as we have a Monoid instance

If you haven't already read my post about Semigroups I suggest you do so now :) Semigroup provides combine(x: A, y: A): A so we can easily combine Integers, Strings etc. In my semigroup example I showed how we can use Semigroups along with recursion or fold() to combine a collection of elements together.

Let's take another look at the example using a fold:

def combineStrings(collection: Seq[String]): String = {
  collection.foldLeft("")(Semigroup[String].combine)
}

foldLeft() needs a "fallback" value, in this case I'm passing an empty String (""). My recursive example also needs the same fallback value:

def combineStrings(collection: Seq[String], acc: String = ""): String = ???

Again I'm using an empty String. Why do we need this?

Identity/Empty element

The answer is in the types: combineStrings() takes a Seq[String]. The Seq can be empty but we still need to return a String. In our example if we pass an empty Seq we get the empty String back. The empty String we're passing here is known as the identity or empty value, we can think of it as a fallback value.

A Monoid is simply a Semigroup with an Empty element

Lets look at the signature of the Monoid type class

trait Monoid[A] {
  def combine(x: A, y: A): A
  def empty: A  
}

This simple addition to Semigroup is actually really useful as it lets us write generic code e.g.

def combineAnything[A](collection: Seq[A])(implicit ev: Monoid[A]): A = {
  val instance = Monoid[A]
  collection.foldLeft(instance.empty)(instance.combine)
}

So long as we have a Monoid instance in scope for A we can handle it. We can even write a very basic map-reduce framework!

def mapReduce[A, B](collection: Seq[A])(op: A => B)(implicit ev: Monoid[B]): B = {
  val instance = Monoid[B]
  collection.map(op).foldLeft(instance.empty)(instance.combine)
}

import cats.instances.int._ // Monoid implementation for ints
val result = mapReduce(Seq(1, 2, 3)) { _ * 2 }

Identity/Empty in detail

As you might expect there's a little more to the identity/empty element than meets the eye! In simple terms the identity element should be a no-op in context of combine() i.e. combine(x, empty) == combine(empty, x) == x

Looking at some examples helps to clarify this:

// Integer addition using 0 as an identity
1 + 0 == 0 + 1 == 1

// Integer multiplication using 1 as an identity
2 * 1 == 1 * 2 == 2

// Integer multiplication using 0 as an identity
2 * 0 == 0 * 2 // Ok 
2 * 0 == 2 // Ouch! 0 != 2 

So it's clear the empty/identity element depends on the context not just on the type. That's why Monoid (and Semigroup) implementations are specific not only to the type but also the combine operation