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 List[Int] to produce an Int if the List is empty? What is the result? How about List[String] => String. Logically we would expect zero for the Int example and "" for the String but how do we represent this?

You can find complete examples of the concepts discussed on my blog in my Github repo . In particular, check out the Monoid example

Introduction

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 default or 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?

The 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 or default 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 monoid = Monoid[A]
  collection.foldLeft(monoid.empty)(monoid.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 monoid = Monoid[B]
  collection.map(op).foldLeft(monoid.empty)(monoid.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 (not ok!)
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