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 schemelike 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)
1 2 

Another way to construct it is:
1 2 

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 foldleft
and foldright
would give the same result in this case.
Settheoretic 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
 Dan Piponi (SIGFPE) wrote a lot of good stuff about monoids in haskell at his blog ‘A Neighborhood of Infinity
 Pete Clark wrote a good introduction to semigroups and monoids on his UGA website