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.
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
(+ (+ (+ (+ 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
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
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
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
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.
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
keyword arguments for more flexibility.