a blog on computing, structure and math

Monoids in Scheme

There is a structure in abstract algebra called a monoid. There are several ways to define a monoid, but before we start, we should answer the obvious question: why should you care?

The reason being aware of monoids is important is that they are everywhere, and knowing the properties of general monoids will lead to better understanding of their specific manifestations, such as the accumulator pattern or string concatenation. I’ll give a good example to start out with: linked lists.

For the sake of simplicity, I am going to use scheme lists and the append operation. In Section 2.2 of SICP, the closure property of was defined. This is distinct from the notion of closure of an expression over the surrounding environment.

An operation # is said to be ‘closed’ in the sense that given two values A and B of the same type, the expression A # B is a value of the same type. In scheme-like prefix notation, we would write (# A B).

Given a list A and a list B, we can concatenate the two lists and get a new list, (append A B)

(append (append '(a) '(b)) '(c))
; => (a b c)

Another way to construct it is:

(append '(a) (append '(b) '(c)))
; => (a b c)

The fact that (a b c) can be constructed in either way means that append is an associative operation, and readers of this blog should recognize that fold-left and fold-right would give the same result in this case.

Set-theoretic Definition of a monoid

This leads to the first two properties that define a general monoid, a monoid is:

Note: the closure property is implicit in the defintion of the operation as a function, since it is impossible for the output of the function to be anything outside of M.

The set M has an identity element e in M, it is defined by:

From the three properties that define of monoids (closure, associativity, identity), we can prove the uniqueness of the identity element:

Suppose a and b are identity elements, then:

This applies to all monoids, in our example, the set M is the set of all Scheme lists, the operation is append, and the unique identity element is the empty list.

Further Reading