Suppose you satisfy these axioms:
- you have a binary function • and a set that • is closed
over (i.e. for all x, y in the
set, x•y is in the set)
- • is associative, ((a • b) • c) = (a • (b • c))
- There is an an identity element I: a • I = I • a =
a
Then • is called a semigroup or “monoid”.
Monoids come from abstract algebra, but they are ubiquitous in
computer science. Here are some monoids: string-append over
strings, addition over integers, state transition over machine
states, compose over unary functions.
Alternatively, we can define a monoid as a binary function • that
is closed under folds fold-left or fold-right.
That is, (fold-left #’• I list-of-set-elements) is an
element of the set. Folds abstract the processing lists of set
elements. The walk through the list, the end test, and the
accumulation of the result are all taken care of by the
implementation of fold. You get to focus on the monoid that acts
on each element.
Folds come in two flavors: fold-left
and fold-right. fold-left has an obvious
iterative implementation, but the result is accumulated left to
right, which can come out backwards. fold-right has an
obvious recursive implementation which accumulates right to left,
The result comes out in the right order, but the recursion can
cause problems if the stack space is limited.
Here are some stupid tricks you can do with folds and monoids.
Create n-ary functions
If we curry the call to fold, we extend the binary function of two
arguments to an n-ary function of a list of arguments. For example,
n-ary addition is just a fold over binary
addition. (fold-left #’+ 0 list-of-integers).
Likewise, n-ary compose is just a fold over
binary compose.
Fold-… is self documenting
If I haven’t used fold-left or fold-right
in a while, I sometimes forget which one computes what.
But fold-left and fold-right can document
themselves: use a combining function that returns the list (F a
b) to indicate a call to F:
> (fold-left (lambda (a b) (list ’F a b)) ’|...| ’(c b a))
(F (F (F |...| C) B) A)
> (fold-right (lambda (a b) (list ’F a b)) ’(a b c) ’|...|)
(F A (F B (F C |...|)))
You can see the structure of the recursion by
using list as the combining function:
> (fold-left #’list ’|...| ’(c b a))
(((|...| C) B) A)
> (fold-right #’list ’(a b c) ’|...|)
(A (B (C |...|)))
fold-… works on groups
A group is a special case of a monoid where the combining function
is also invertible. fold-… can be used on a
group as well. For example, fold-left can be used on
linear fractional transformations, which are a group under function
composition.
fold-… as an accumulator
The combining function in fold-left must be at least
semi-closed: the output type is the same as the type of the left
input. (In fold-right, the output type is the same as
the type of the right input.) This is so we can use the output of
the prior call as the input to the next call. In effect, we set up
a feedback loop between the output to one of the inputs of the
binary function. This feedback loop has a curious property: it
behaves as if it has state. This is happens even
though both fold-… and the combining functions are pure
functions. The state appears to arise from the feedback loop.
We can use fold-… to accumulate a value.
For fold-left, at each iteration, the accumulator is
passed as the first (left) argument to the combining function while
the next element of the list is the second (right) argument. The combining function returns a new
value for the accumulator (it can return the old value if nothing is to be
accumulated on this step). The result of the fold-left
is the final value of the accumulator.
Note that because the accumulated value is passed as the first
argument, you cannot use cons as the combining function
to accumulate a list. This is unfortunate because it seems obvious
to write (fold-left #’cons ’() ...) to accumulate a
list, but that isn’t how it works. However, if you swap the
arguments to cons you’ll accumulate a list:
(defun xcons (cdr car) (cons car cdr))
(defun revappend (elements base)
(fold-left #’xcons base elements))
fold-… as a state machine
Although fold-left is commonly used to accumulate
results, it is more general than that. We can
use fold-left as a driver for a state machine. The second
argument to fold-left is the initial state, and the
combining function is the state transition function. The list
argument provides a single input to the state machine on each state
transition.
For example, suppose you have a data structure that is a made out
of nested plists. You want to navigate down through the plists to
reach a final leaf value. We set up a state machine where the
state is the location in the nested plists and the state transition
is navigation to a deeper plist.
(defun getf* (nested-plists path)
(fold-left #’getf nested-plists path))
Alternatively, we could drive a state machine by
calling fold-left with an initial state and list of
state transtion functions:
(defun run-state-machine (initial-state transitions)
(fold-left (lambda (state transition)
(funcall transition state))
initial-state
transitions))
Visualizing fold-left
If we unroll the recursion in fold-left, and introduce
a temp variable to hold the intermediate result, we see the
following:
(fold-left F init ’(c b a))
temp ← init
temp ← F(temp, c)
temp ← F(temp, b)
temp ← F(temp, a)
I often find it easier to write the combining function in
a fold-… by visualizing a chain of combining
functions wired together like this.
Generating pipelines
Now let’s partially apply F to its right argument. We do this by
currying F and immediately supplying an argument:
(defun curry-left (f)
(lambda (l)
(lambda (r)
(funcall f l r))))
(defun curry-right (f)
(lambda (r)
(lambda (l)
(funcall f l r))))
(defun partially-apply-left (f l)
(funcall (curry-left f) l))
(defun partially-apply-right (f r)
(funcall (curry-right f) r))
We can partially apply the combining function to the elements in
the list. This gives us a list of one argument functions. In fact,
for each set element in the set associated with our monoid, we can
associate a one-argument function. We can draw from this set of
one-argument functions to create pipelines through function
composition. So our visualization
temp ← init
temp ← F(temp, c)
temp ← F(temp, b)
temp ← F(temp, a)
becomes
temp ← init
temp ← Fc(temp)
temp ← Fb(temp)
temp ← Fa(temp)
We can write this pipeline this way:
result ← Fa ← Fb ← Fc ← init
or this way:
result ← (compose Fa Fb Fc) ← init
We can pretend that the elements of the set associated with monoid
are pipeline stages. We can treat lists of set elements as
though they are pipelines.
Notice how we never write a loop. We don’t have the
typical list loop boilerplate
(if (null list)
... base case ...
(let ((element (car list))
(tail (cdr list)))
... ad hoc per element code ...
(iter tail)))
Instead, we have a function that processes one element at a time
and we “lift” that function up to process lists of
elements.
Pipelines are easier to reason about than loops. fold-… converts loops into pipelines.
It takes a little practice to use fold-… in the less obvious ways.
Once you get used to it, you’ll see them everywhere. You can eliminate many loops by replacing them with fold-….
Monoids vs. Monads
A monad is a monoid over a set of curried functions. You use a variant of compose to combine the curried functions. Monads force sequential processing because you set up a pipeline and the earlier stages of the pipeline naturally must run first. That is why monads are used in lazy languages to embed imperative subroutines.
