fold-… and monoids

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.