I’m often asked about monoids, monads, and what the difference is between the two. Seeing that there’s not a lot of material that explains these things in terms of Scala, I’m going to try to remedy that presently. Even if you already know what these things are, I hope to provide a little deeper insight. In this post I’m going to talk about monoids in some depth.

First, here is a definition for Monoid, in Scala:

trait Monoid[T] { def append(m1: T, m2: T): T val identity: T }

To state that in English, a monoid is given by a type T together with a function `append: (T, T) => T`

, and a value `identity: T`

. The rules for a monoid are that `append`

must be associative (meaning that `append(x, append(y, z)) == append(append(x, y), z))`

, and `identity`

must be an identity for that function (such that `append(identity, x) == x`

, and `append(x, identity) == x`

. For example, `String`

with concatenation and the empty string form a monoid. `Boolean`

with `true`

and `&&`

, or `Boolean`

with `false`

and `||`

, also are monoids. As are `Int`

with addition and `0`

, multiplication and `1`

, etc.

As an example, here is the String monoid:

val stringMonoid = new Monoid[String] { def append(s1: String, s2: String) = s1 + s2 val identity = "" }

**Monoids are List-Algebras**

Everyone is familiar with the singly-linked list (a.k.a. cons-list). A `List[T]`

is constructed as either the empty list (`Nil`

), or from an element of type `T`

and another `List[T]`

.

`Nil`

is an irreducible unit (it takes no arguments and has no structure), and is in fact totally equivalent to the `()`

value of type `Unit`

. The `::`

(cons) constructor takes two arguments, and indeed a non-empty `List[T]`

is equivalent to a pair `(T, List[T])`

(the head and the tail).

Note that a Monoid consists of two functions, one that takes no arguments, and one that takes two arguments, just like the constructors of `List`

. This is not a coincidence. If you have a `List[T]`

and a `Monoid[T]`

, you can reduce the list using the Monoid, to a single value of type `T`

.

def reduce[A](ts: List[A], m: Monoid[A]): A = ts match { case Nil => m.identity case x :: xs => m.append(x, reduce(xs)) }

If you expand out the Monoid argument, you get:

def reduce[A](ts: List[A], identity: A, append: (A, A) => A): A

This looks suspicously similar to foldRight and foldLeft. Again, not a coincidence. Here’s the signature for foldRight:

def foldRight[A,B](ts: List[A], identity: B, append: (A, B) => B): B

In fact, the implementation of these last two is exactly identical. So, monoids are just an abstraction that represents the arguments you give to folds. The associativity rule simply models the fact that you should get the same answer for a given monoid whether you foldLeft or foldRight. The identity rule (in loose terms) models the fact that the empty list “doesn’t count”.

**Monoids are one-object categories**

Those readers further along might be wondering where this notion of monoids comes from, and why the concept is even warranted in the first place. Well, it comes from Category Theory. So let me give you a crash course.

A category consists of objects (`A`

, `B`

, `C`

, etc.) and arrows between objects, (`A => B`

, `A => C`

, `B => C`

, etc). You can think of it as a diagram or graph, with objects as the nodes, and arrows as directed edges between the nodes. Given any pair of arrows `f: B => C`

and `g: A => B`

, there exists a composite arrow `(f * g): A => C`

.

Here’s an encoding of the concept in Scala:

trait Category[F[_,_]] { def compose[A,B,C](f: F[B,C], g: F[A,B]): F[A,C] def identity[A]: F[A,A] }

For example, there’s a category where the objects are Scala types, the arrows are Scala functions, and the composition of arrows is simply function composition.

val catScala = new Category[Function1] { def compose[A,B,C](f: B => C, g: A => B): A => C = f compose g def identity[A]: A => A = (a: A) => a }

A category must have an identity arrow for each object, which points from the object to itself. In the Scala category, these arrows are represented by the identity function.

Furthermore, a category must satisfy associativity (`(f * g) * h == f * (g * h)`

), and identity (`f * identity == f`

and `identity * f == f`

), for all arrows `f`

, `g`

, and `h`

.

Note that the laws that a category must satisfy are exactly the laws that a monoid must satisfy. You can think of the `append`

function of the monoid as the arrow composition, and the identity value as the identity arrow. For a `Monoid[T]`

, the arrows are precisely all the values of type `T`

, and `T`

itself is the only object in the category.

We can give this category in Scala:

// The category for a given monoid. def monoidCategory[M](m: Monoid[M]) = new Category[({type λ[α, β] = M})#λ] { def identity[A] = m.identity def compose[X, Y, Z](f: M, g: M) = m.append(f, g) }

Something I’ve always wondered is, what is the name of the generalization of a monoid that encodes the arguments to any fold? Such as:

trait Semioid[A, B] {

def identity: A

def sappend(a: A, b: B): A

}

then a monoid is just

trait Moniod[A] extends Semioid[A,A]

Nuttycom: It a model of a theorem

`List[A] => B`

, whereas a Monoid models`List[A] => A`

. There are really only two ways that you can do`List[A] => B`

(i.e. only two implementations of your “Semioid”). You can either map`(A => B)`

over the list, and then reduce with a monoid`B`

, or you can reduce the list to`A`

(if`A`

is a monoid), and then apply a function`(A => B)`

to the result.I.e. if you have:

The only two ways to reduce a list are:

1) a(list.map(f))

2) f(a(list))

A monoid is just the “a” part. Your Semioid is the “f” in addition. So I guess it models a hylomorphism, since it’s simultaneously a List-algebra and a B-coalgebra. I would just call it a “fold”.

Fold is a good name. Thanks! The reason I wondered about this is that I find I have a frequent need to lift a Semigroup[A] into a Fold[Option[A], A] for reductions of possibly-empty lists.

Another handy construct is this (hat tip to Ed Kmett):

This models a mapping from some type A into a monoid B, and reduction using that monoid. It also lets you override cons or snoc with a more efficient implementation.

You can always lift a Semigroup[A] into a Monoid[Option[A]].

Nuttycom: Wikipedia says that your “semioid” is actually called a “monoid action”, “monoid act”, or “operator monoid”. I’m inclined to call the trait “MAct”.

Would you explain how this models a hylomorphism? Is “f” the unfold?

Yes, f is the anamorphism in that case.

Thanks Rúnar, I’m looking forward to a blog on Monads!

Pingback: More on Monoids and Monads « Apocalisp

A monoid’s append takes two As and returns an A whereas the function given to fold takes an A and a B and returns B. Therefore I don’t understand So, monoids are just an abstraction that represents the arguments you give to folds.

Heiko,

In the case where you’re folding with a monoid, A will be the same type as B. That is, your list will contain Bs, and you will be folding it with a Monoid[B]. However, if your List contains As, and there is no Monoid[A] with which to fold, you will want to turn all the As into some B, where you have a Monoid[B]. Of course, (B => B) is always a monoid. So if you look at the signature for foldRight (slightly curried):

def foldRight[A,B](f: A => (B => B), as: List[A]): B => B

This is actually not the most general signature.

`B => B`

is just one particular monoid, but really, we should be able to use any monoid at all:def foldMap[A, B:Monoid](f: A => B, as: List[A]): B

This is much more clear when you think of the

monadfor monoids (see the most recent post). I.e, if you have a transform`A => B`

you can always turn a List[A] into a List[B] (see the map function). Then you have a List[B] which you can reduce, given Monoid[B]. Of course, you don’t have to map and reduce in that specific order (in practise, you do the mapping and reduction simultaneously in one pass over the list, which is exactly what foldRight does).Pingback: Reading More About Type-Classes and Scala « Statically Typed