Instantly share code, notes, and snippets.

# Monoids

A monoid is a type for which there exists:

1. an associative binary operation, let's call it `combine`
2. an identity element, let's call it `neutral`

Please note that it's the combination of an operation valid for that type with a particular instance of that type that forms a monoid, not just a type alone.

See the last section — Laws — for rationale behind the naming for `neutral` and `combine`.

## Examples

These are just a few example, a lot of types form monoids.

• type: numbers
• `combine`: `+`
• `neutral`: `0`

#### 2. Multiplication Monoid

• type: numbers
• `combine`: `*`
• `neutral`: `1`

#### 3. Conjunction Monoid

• type: booleans
• `combine`: `and`
• `neutral`: `true`

#### 4. Disjunction Monoid

• type: booleans
• `combine`: `or`
• `neutral`: `false`

## Purpose

Why are these useful? Suppose you want to sum all the numebers in a list:

```(defn sum [nums] (reduce #(+ %1 %2) 0 nums))
(sum [])      ;; 0
(sum [1 2 3]) ;; 1```

Or suppose you want a product of all the numbers in a list:

```(defn product [nums] (reduce #(* %1 %2) 1 nums))
(product [])      ;; 1
(product [1 2 3]) ;; 6```

Or suppose you want to determine whether all the elements of a list validate a certain condition:

```(defn forall [bools] (reduce #(and %1 %2) true bools))
(forall (map even? [1 2 3])) ;; false
(forall (map even? [2 4 6])) ;; true```

Or that at least one element validates the condition

```(defn exists [bools] (reduce #(or %1 %2) false bools))
(exists (map even? [1 3 5])) ;; false
(exists (map even? [1 2 3])) ;; true```

All the examples I've show exhibit some code duplication. The reduce part is similar except for the reduce operation we're calling and the initial element.

This is exactly what a monoid offers you, that combining operation — `combine` — and a start element which is "neutral" to the end result — `neutral`.

In statically typed languages these two operations are separate, but Clojure was able to leverage the fact that it's a dynamically typed language and decided to expose the `neutral` element by having a zero-argument overload for the `combine` operation. That's why...

```user=> (+)
0
user=> (*)
1
user=> (and)
true
user=> (or)
nil```

Well... I don't really know why `or` returns `nil` instead of `false`, but `nil` still a "falsy" value.

We can now factor our that duplication:

```(defn monoid-reduce [op xs] (reduce op (op) xs))

(defn sum [nums] (monoid-reduce + nums))
(defn product [nums] (monoid-reduce * nums))
;; This won't work because macros are not first-class values, but you get the
;; point.
(defn forall [bools] (monoid-reduce and bools))
(defn exists [bools] (monoid-reduce or bools))```

## Laws

A valid monoid should also obey these properties (also called laws), which is why the identity element for `+` is `0` and not `1`. Same for the other examples I've given.

• `combine(neutral, x) = x`
• `combine(x, neutral) = x`
• `combine(x, combine(y, z)) = combine(combine(x, y), z)`

### gigasquid commented Nov 7, 2014

 awesome writeup! Thanks :)

### cbegin commented Nov 11, 2014

 good read. one minor typo: ``````(sum [1 2 3]) ;; 1 `````` Should be 6.