Reduce vs fold in Common Lisp

Introduction

If you have already used functional languages, you are probably familiar with fold, a high order function used to iterate on a collection of values to combine them and return a result. You may be surprised that Common Lisp does not have a fold function, but provides REDUCE which works a bit differently. Let us see how they differ.

Understanding REDUCE

In its simplest form, REDUCE accepts a function and a sequence (meaning either a list or a vector). It then applies the function to successive pairs of sequence elements.

You can easily check what happens by tracing the function:

CL-USER> (trace +)
CL-USER> (reduce #'+ '(1 2 3 4 5))
  0: (+ 1 2)
  0: + returned 3
  0: (+ 3 3)
  0: + returned 6
  0: (+ 6 4)
  0: + returned 10
  0: (+ 10 5)
  0: + returned 15
15

In this example, the call to REDUCE evaluates (+ (+ (+ (+ 1 2) 3) 4) 5).

You can reverse the order using the :from-end keyword argument:

CL-USER> (trace +)
CL-USER> (reduce #'+ '(1 2 3 4 5) :from-end t)
  0: (+ 4 5)
  0: + returned 9
  0: (+ 3 9)
  0: + returned 12
  0: (+ 2 12)
  0: + returned 14
  0: (+ 1 14)
  0: + returned 15
15

In which case you will evaluate (+ 1 (+ 2 (+ 3 (+ 4 5)))). The result is of course the same since the + function is associative.

You can of course provide an initial value, in which case REDUCE will behave as if this value has been present at the beginning (or the end with :from-end) of the sequence.

The surprising aspect of REDUCE is its behaviour when called on a sequence with less than two elements:

• If the sequence contains a single element:
  • if there is no initial value, the function is not called and the element is returned directly;
  • if there is one, the function is called on both the initial value and the single element.
• If the sequence is empty:
  • if there is no initial value, the function is called without any argument;
  • if there is one, the function is not called and the initial value is returned directly.

As a result, any function passed to REDUCE must be able to handle being called with zero, one or two arguments. Most examples found on the Internet use + or append, and these functions happen to handle it (e.g. (+) returns the identity element of the addition, zero). If you write your own functions, you will have to deal with it using the &OPTIONAL lambda list keyword.

This can lead to unexpected behaviours. If you compute the sum of a sequence of floats using (reduce #'+ floats), you may find it logical to obtain a float. But if FLOATS is an empty sequence, you will get 0 which is not a float. Something to keep in mind.

Differences with fold

The fold function is traditionally defined as accepting three arguments: a function, an initial value — or accumulator — and a list. The function is called repeatedly with both the accumulator and a list element, using the value returned by the function as next accumulator.

For example in Erlang:

lists:foldl(fun(X, Sum) -> Sum + X end, 0, [1, 2, 3, 4, 5]).

An interesting consequence is that fold functions are always called with the same type of arguments (the list value and the accumulator), while REDUCE functions can be called with zero or two list values. This makes it harder to write functions when the accumulated value has a different type from sequence values.

Fold is also simpler than REDUCE since it does not have any special case, making it easier to reason about its behaviour.

It would be interesting to know why a function as fundamental as fold was not included in the Common Lisp standard.

Implementing FOLDL

We can of course implement a fold function in Common Lisp. We will concentrate on the most common (and most efficient) left-to-right version. Let us start by a simple implementation for lists:

(defun foldl/list (function value list)
  (declare (type (or function symbol) function)
           (type list list))
  (if list
      (foldl/list function (funcall function value (car list)) (cdr list))
      value))

As clearly visible, the recursive call to FOLDL/LIST is in tail position and SBCL will happily perform tail-call elimination.

For vectors we use an iterative approach:

(defun foldl/vector (function value vector)
  (declare (type (or function symbol) function)
           (type vector vector))
  (do ((i 0 (1+ i))
       (accumulator value))
      ((>= i (length vector))
       accumulator)
    (setf accumulator (funcall function accumulator (aref vector i)))))

Finally we write the main FOLDL function which operates on any sequence:

(defun foldl (function value sequence)
  (declare (type (or function symbol) function)
           (type sequence sequence))
  (etypecase sequence
    (list (foldl/list function value sequence))
    (vector (foldl/vector function value sequence))))

At the point we can already use FOLDL for various operations. We could of course improve it with the addition of the usual :START, :END and :KEY keyword arguments for more flexibility.