pema.dev

What the hell is a monoid

For some reason, I keep getting asked the same few questions about common constructs in functional programming. I want a page to point friends towards. That is what this is. Without further ado, welcome to the 999th terrible monad tutorial.

What is a monoid

A monoid is a set equipped with an associative binary operation and a neutral element.

For those who may not remember, the associative property holds for an operator ‘\(\oplus\)’ if it is the case that \((a \oplus b) \oplus c = a \oplus (b \oplus c)\).

A neutral element is an element ‘\(z\)’ of the set such that \(a \oplus z = z \oplus a = a\).

Here are some examples of monoids, specified as (the set, the operator, the neutral element):

  • (integers, +, 0)
  • (integers, *, 1)
  • (strings, string concatenation, the empty string)
  • (lists, list concatenation, the empty list)
  • (functions, function composition, identity function)

What is a functor

A functor is, essentially, a data structure containing values of some generic type, and which can be mapped over. In Haskell, the function to perform the mapping is called fmap and has type

Functor f => (a -> b) -> f a -> f b

in Haskell. In some kind of pseudo-C#, it’s signature could look like

Functor<B> fmap<A, B>(Func<A, B> mapper, Functor<A> val) { ... }

For those who struggle to read that, this means that the function takes 2 arguments:

  • A function from type a to type b
  • A functor containing type a And returns a functor containing type b. The f in this type signature is the functor.

A simple example of a functor is a list. A list can:

  • Contain values of any type
  • Be mapped over with some function to produce a new list containing values of a different type

Another example are optional types which are prevalent in many functional languages. Optional types (Maybe in Haskell), either contain a value of some generic type, or containing no value at all. They are useful for writing functions that may or may not fail to produce a meaningful output. They are also functors since they can:

  • Contain one value of any type
  • Be mapped over with some function to produce an optional type containing one value of a different type. Concretely, if the optional type represents an actual value, we apply the function that value and wrap the result in another optional type. If the optional type contains no value, we do nothing to it.

Mapping over a data structure like this is a very common operation, so it makes sense to have an abstraction for it.

What is a monad

Note: This explanation may raise some eyebrows among those who know the topic well, but I really hate how most people are introduced to monads.

In one sentence, monads as they relate to programming are a design pattern that makes it simple to chain operations together while hiding a lot of the tedious boilerplate code involved in doing so.

More specifically, a monad is, like a functor, a data structure that contains values of some generic type. In fact, all monads are also functors. In addition to being functors, monads implement 2 useful operations which we’ll call pure and bind.

pure takes some value and returns that value wrapped inside of the monad. It is used to produce monadic values from non-monadic ones. pure has type

Monad m => a -> m a

In pseudo-C#, it would look like

Monad<A> pure<A>(A val) { ... }

bind takes as input a monadic value, and a function from a non-monadic value to a monadic one containing a different type, and returns a monadic value of the second type. In Haskell, it’s type is

Monad m => m a -> (a -> m b) -> m b

And as usual, in pseudo-C# it would look like:

Monad<B> bind<A, B>(Monad<A> val, Func<A, Monad<B>> binder) { ... }

Monads by example

The above explains briefly what a monad is, but not what it is useful for. Monads are used in functional languages to perform effectful computations without wanting to kill oneself. Examples of effectful computations are:

  • Computations that may or may not return a value (yep, optional types form a monad)
  • Computations that may read or write to a console or to disk
  • Computations which may write activity to a log
  • Computations which may return any amount of values
  • Computations which may interact with a piece of mutable state … and many more. Roughly, any time a computation is more than a simple deterministic mapping from an input to an output, we call it effectful.

Problems arise when trying to compose effectful operations in a purely functional way. To illustrate this, I’ll use the aforementiond example of writing activity to a log. I’ll use JavaScript for code demos since it is should be fairly easy to understand for people without too much knowledge in functional programming. Imagine we have a tiny program that does a sequence of numerical operations on a number, such as adding 5 to it, or multiplying it by 2:

function add5(a) {
  return a + 5
}

function mul2(a) {
  return a * 2
}

let res0 = 1
let res1 = add5(res0)
let res2 = mul2(res1)
let res3 = add5(res2)
console.log(res3)

This snippet declares a function for each of those 2 operations, and then performs them a few time. It calculates “((1 + 5) * 2) + 5” and prints the result - “17”. Now, let’s say we want to add logging to our program. In many imperative languages, one choice would be to have a global string variable for our log somewhere, and then have each function write to it, but in functional programming we avoid using mutable state. Therefore, the most straight forward way is to have each function return both the calculated number, and an string representing a log entry. Let’s implement that:

function add5(a) {
  return {val: a + 5, log: "Added 5\n"}
}

function mul2(a) {
  return {val: a * 2, log: "Multiplied by 2\n"}
}

let res0 = 1
let res1 = add5(res0)
let res2 = mul2(res1)
let res3 = add5(res2)
console.log(res3)

This program no longer produces the desired output! In a strongly typed language, it wouldn’t compile at all! The issue is that we are chaining functions, feeding the result of the first to the next, but each function returns a tuple but expects a single value as input. Essentially, add5 and mul2 have become effectful computations. Let’s fix that by implementing our aformentioned bind and pure operations:

function pure(val) {
  return {val: val, log:""}
}

function bind(input, binder) {
  let log1 = input.log
  let val1 = input.val
  let res = binder(val1)
  let log2 = res.log
  let val2 = res.val
  return {val: val2, log: log1 + log2}
}

function add5(a) {
  return {val: a + 5, log: "Added 5\n"}
}

function mul2(a) {
  return {val: a * 2, log: "Multiplied by 2\n"}
}

let res0 = pure(1)
let res1 = bind(res0, add5)
let res2 = bind(res1, mul2)
let res3 = bind(res2, add5)
console.log(res3)

Now, any time we want to use the result of one computation as the input to another, we can use bind to chain them. The program produces the desired result when run, a value and the final log:

{val: 17, log: 'Added 5\nMultiplied by 2\nAdded 5\n'}

It should be fairly clear to see how this is a pattern applicable in many cases beyond the one described here. For example, if the problem we were solving was instead that each of our math operations may fail to produce a value, we could swap out the bind and pure function but leave the using code exactly the same, and everything would still work as intended! In JavaScript, the code for that usecase might look something like, using null to represent the absense of a value:

function pure(val) {
  return val
}

function bind(input, binder) {
  if (input == null) {
    return null
  } else {
    return binder(input)
  }
}

Worth noting also is that the type contained within the monad (integers in the previous example) doesn’t have to always be the same for this to work. Let’s illustrate that with one last code example. We’ll add to our logging-example a function that converts a number to a string, and a function that concatenates a string with itself:

function toStr(a) {
  return {val: a.toString(), log: "Converted to string\n"}
}

function concat(a) {
  return {val: a + ", " + a, log: "Concatenated strings\n"}
}

And change the using code to:

let res0 = pure(1)
let res1 = bind(res0, add5)
let res2 = bind(res1, mul2)
let res3 = bind(res2, toStr)
let res4 = bind(res3, concat)
console.log(res4)

Which will now print

{
  log: "Added 5\nMultiplied by 2\nConverted to string\nConcatenated strings\n"
  val: "12, 12"
}

Notice how the exact same way of writing user code still functions perfectly even when mixing both integer and string types.

Notes

  • All monads are applicatives
  • All applicatives are functors
  • A monoid without a neutral element is called a semigroup

Worth noting that these are just a small sampling of useful abstractions plucked from category theory, and many more exist, though most of the literature on them is likely needlessly complicated for what they actually do. These are the ones I get asked about the most.

What does it mean that a monad is a monoid in the category of endofunctors

It’s not important. Stop asking.

If you really care, read this.

Links

https://wiki.haskell.org/All_About_Monads

http://learnyouahaskell.com/a-fistful-of-monads

https://stackoverflow.com/a/194207