monoids.md

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.

1. Addition Monoid

• 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)

awesome writeup! Thanks :)

good read. one minor typo:

(sum [1 2 3]) ;; 1

Should be 6.