We define the reversal of a list L to be a list containing exactly the elements of L in reversed order. The Common LISP built-in function (reverse L) returns the reversal of L:
USER(1): (reverse '(1 2 3 4)) (4 3 2 1) USER(2): (reverse '(1 (a b) (c d) 4)) (4 (c d) (a b) 1) USER(3): (reverse nil) NIL
Implementing a version of reverse is not difficult, but finding an efficient implementation is not as trivial. To review what we learned in the last tutorial, let us begin with a naive implementation of reverse:
(defun slow-list-reverse (L)
"Create a new list containing the elements of L in reversed order."
(if (null L)
nil
(list-append (slow-list-reverse (rest L))
(list (first L)))))
Notice that this linearly recursive implementation calls the function list-append we implemented in the the last tutorial. Notice also the new function list, which returns a list containing its arguments. For example, (list 1 2) returns the list (1 2). In general, (list x1 x2 ... xn) is just a shorthand for (cons x1 (cons x2 ... (cons xn nil) ... )). So, the expression (list (first L)) in the listing above returns a singleton list containing the first element of L.
So, why does (slow-list-reverse L) returns the reversal of L? The list L is constructed either by nil or by cons:
Let us trace the execution of the function to see how the recursive calls unfold:
USER(3): (trace slow-list-reverse)
(SLOW-LIST-REVERSE)
USER(4): (slow-list-reverse '(1 2 3 4))
0: (SLOW-LIST-REVERSE (1 2 3 4))
1: (SLOW-LIST-REVERSE (2 3 4))
2: (SLOW-LIST-REVERSE (3 4))
3: (SLOW-LIST-REVERSE (4))
4: (SLOW-LIST-REVERSE NIL)
4: returned NIL
3: returned (4)
2: returned (4 3)
1: returned (4 3 2)
0: returned (4 3 2 1)
(4 3 2 1)
Everything looks fine, until we trace also the unfolding of list-append:
USER(9): (trace list-append)
(LIST-APPEND)
USER(10): (slow-list-reverse '(1 2 3 4))
0: (SLOW-LIST-REVERSE (1 2 3 4))
1: (SLOW-LIST-REVERSE (2 3 4))
2: (SLOW-LIST-REVERSE (3 4))
3: (SLOW-LIST-REVERSE (4))
4: (SLOW-LIST-REVERSE NIL)
4: returned NIL
4: (LIST-APPEND NIL (4))
4: returned (4)
3: returned (4)
3: (LIST-APPEND (4) (3))
4: (LIST-APPEND NIL (3))
4: returned (3)
3: returned (4 3)
2: returned (4 3)
2: (LIST-APPEND (4 3) (2))
3: (LIST-APPEND (3) (2))
4: (LIST-APPEND NIL (2))
4: returned (2)
3: returned (3 2)
2: returned (4 3 2)
1: returned (4 3 2)
1: (LIST-APPEND (4 3 2) (1))
2: (LIST-APPEND (3 2) (1))
3: (LIST-APPEND (2) (1))
4: (LIST-APPEND NIL (1))
4: returned (1)
3: returned (2 1)
2: returned (3 2 1)
1: returned (4 3 2 1)
0: returned (4 3 2 1)
(4 3 2 1)
What we see here is revealing: given a list of N element,
slow-list-reverse makes O(N) recursive calls,
with each level of recursionl involving a call to the linear-time
function list-append. The result is that slow-list-reverse
is an O(N2) function.
We can in fact build a much more efficient version of reverse using auxiliary functions and accumulator variables:
(defun list-reverse (L)
"Create a new list containing the elements of L in reversed order."
(list-reverse-aux L nil))
(defun list-reverse-aux (L A)
"Append list A to the reversal of list L."
(if (null L)
A
(list-reverse-aux (rest L) (cons (first L) A))))
The function list-reverse-aux is an auxiliary function (or a helper function). It does not perform any useful function by itself, but the driver function list-reverse could use it as a tool when building a reversal. Specifically, (list-reverse-aux L A) returns a new list obtained by appending list A to the reversal of list L. By passing nil as A to list-reverse-aux, the driver function list-reverse obtains the reversal of L.
Let us articulate why (list-reverse-aux L A) correctly appends A to the reversal of list L. Again, we know that either L is nil or it is constructed by cons:
USER(17): (trace list-reverse list-reverse-aux)
(LIST-REVERSE LIST-REVERSE-AUX)
USER(18): (list-reverse '(1 2 3 4))
0: (LIST-REVERSE (1 2 3 4))
1: (LIST-REVERSE-AUX (1 2 3 4) NIL)
2: (LIST-REVERSE-AUX (2 3 4) (1))
3: (LIST-REVERSE-AUX (3 4) (2 1))
4: (LIST-REVERSE-AUX (4) (3 2 1))
5: (LIST-REVERSE-AUX NIL (4 3 2 1))
5: returned (4 3 2 1)
4: returned (4 3 2 1)
3: returned (4 3 2 1)
2: returned (4 3 2 1)
1: returned (4 3 2 1)
0: returned (4 3 2 1)
(4 3 2 1)
For each recursive call to list-reverse-aux, notice how the first element of L is "peeled off", and is then "accumulated" in A. Because of this observation, we call the variable A an accumulator variable.
To better understand how auxiliary functions and accumulator variables are used, let us revisit the problem of computing factorials. The following is an alternative implementation of the factorial function:
(defun fast-factorial (N)
"A tail-recursive version of factorial."
(fast-factorial-aux N 1))
(defun fast-factorial-aux (N A)
"Multiply A by the factorial of N."
(if (= N 1)
A
(fast-factorial-aux (- N 1) (* N A))))
Let us defer the explanation of why the function is named "fast-factorial", and treat it as just another way to implement factorial.
Notice the structural similarity between this pair of functions and
those for computing list reversal.
The auxiliary function (fast-factorial-aux N A)
computes the product of A and the N'th factorial.
The driver function computes N! by calling
fast-factorial-aux with A set to 1.
Now, the correctness of the auxiliary function
(i.e. that (fast-factorial-aux N A) indeed
returns the product of N! and A) can be established as
follows. N is either one or larger than one.
Tracing both fast-factorial and fast-factorial-aux, we get the following:
USER(3): (trace fast-factorial fast-factorial-aux)
(FAST-FACTORIAL-AUX FAST-FACTORIAL)
USER(4): (fast-factorial 4)
0: (FAST-FACTORIAL 4)
1: (FAST-FACTORIAL-AUX 4 1)
2: (FAST-FACTORIAL-AUX 3 4)
3: (FAST-FACTORIAL-AUX 2 12)
4: (FAST-FACTORIAL-AUX 1 24)
4: returned 24
3: returned 24
2: returned 24
1: returned 24
0: returned 24
24
If we compare the structure of fast-factorial with list-reverse, we notice certain patterns underlying the use of accumulator variables in auxiliary functions:
Now that you understand how fast-factorial works, we explain where the adjective "fast" come from ...
(defun factorial (N)
"Compute the factorial of N."
(if (= N 1)
1
(* N (factorial (- N 1)))))
It is fair to point out that, as recursion unfolds, stack frames
will have to be set up, function arguments will have to be pushed
into the stack, so on and so forth, resulting in unnecessary
runtime overhead not experienced by the iterative counterpart
of the above factorial function:
int factorial(int N) {
int A = 1;
while (N != 1) {
A = A * N;
N = N - 1;
}
return A;
}
Because of this and other excuses, programmers conclude that
they could write off recursive implementations ...
Modern compilers for functional programming languages usually implement tail-recursive call optimizations which automatically translate a certain kind of linear recursion into efficient iterations. A linear recursive function is tail-recursive if the result of each recursive call is returned right away as the value of the function. Let's examine the implementation of fast-factorial again:
(defun fast-factorial (N)
"A tail-recursive version of factorial."
(fast-factorial-aux N 1))
(defun fast-factorial-aux (N A)
"Multiply A by the factorial of N."
(if (= N 1)
A
(fast-factorial-aux (- N 1) (* N A))))
Notice that, in fast-factorial-aux, there is no work left to be done after the recursive call (fast-factorial-aux (- N 1) (* N A)). Consequently, the compiler will not create new stack frame or push arguments, but instead simply bind (- N 1) to N and (* N A) to A, and jump to the beginning of the function. Such optimization effectively renders fast-factorial as efficient as its iterative counterpart. Notice also the striking structural similarity between the two.
When you implement linearly recursive functions, you are encouraged to restructure it as a tail recursion after you have fully debugged your implementation. Doing so allows the compiler to optimize away stack management code. However, you should do so only after you get the prototype function correctly implemented. Notice that the technique of accumulator variables can be used even when we are not transforming code to tail recursions. For some problems, the use of accumulator variables offers the most natural solutions.
A data type is first-class in a programming language when you can pass instances of the data type as function arguments or return them as function values. We are used to treating numeric and Boolean values as first-class data types in languages like Pascal and C. However, we might not be familiar to the notion that functions could be treated as first-class objects, that is, functions can be passed as function arguments and returned as function values. This unique feature of Common LISP and other functional languages makes it easy to build very powerful abstractions. In the remaining of this tutorial, we will look at what passing functional arguments buys us. In the fourth tutorial, when we talk about imperative programming in LISP, we will return to the topic of returning functional values.
Frequently, we need to apply a transformation multiple times on the same data object. For example, we could define the following transformation:
(defun double (x) "Multiple X by 2." (* 2 x))We could compute 24 by applying the double transformation 4 times on 1:
USER(10): (double (double (double (double 1)))) 16Not only is this clumsy, but it also fails to express the very idea that the same transformation is applied multiple times. It would be nice if we can repeat applying a given transformation F on X for N times by simply writing (repeat-transformation F N X). The following function does just that:
(defun repeat-transformation (F N X)
"Repeat applying function F on object X for N times."
(if (zerop N)
X
(repeat-transformation F (1- N) (funcall F X))))
The definition follows the standard tail recursive pattern. Notice
the form (funcall F X). Given
a function F and objects X1
X2 ... Xn,
the form (funcall F X1
X2 ... Xn)
invoke the function F with arguments X1,
X2, ..., Xn. The variable N
is a counter keeping track of the remaining number of times we need to apply
function F to the accumulator variable X.
To pass a the function double as an argument to repeat-transformation, we need to annotate the function name double by a closure constructor, as in the following:
USER(11): (repeat-transformation (function double) 4 1) 16There is nothing magical going on, the closure constructor is just a syntax for telling Common LISP that what follows is a function rather than a local variable name. Had we not included the annotation, Common LISP will treat the name double as a variable name, and then report an error since the name double is not defined.
To see how the evaluation arrives at the result 16, we could, as usual, trace the execution:
USER(12): (trace repeat-transformation) REPEAT-TRANSFORMATION USER(13): (repeat-transformation #'double 4 1) 0: (REPEAT-TRANSFORMATION #4 1) 1: (REPEAT-TRANSFORMATION # 3 2) 2: (REPEAT-TRANSFORMATION # 2 4) 3: (REPEAT-TRANSFORMATION # 1 8) 4: (REPEAT-TRANSFORMATION # 0 16) 4: returned 16 3: returned 16 2: returned 16 1: returned 16 0: returned 16 16
Notice that exponentiation is not the only use of the repeat-transformation function. Let's say we want to build a list containing 10 occurrences of the symbol blah. We can do so with the help of repeat-transformation:
USER(30): (defun prepend-blah (L) (cons 'blah L)) PREPEND-BLAH USER(31): (repeat-transformation (function prepend-blah) 10 nil) (BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH)
Suppose we want to fetch the 7'th element of the list (a b c d e f g h i j). Of course, we could use the built in function seventh to do the job, but for the fun of it, we could also achieve what we want in the following way:
USER(32): (first (repeat-transformation (function rest) 6 '(a b c d e f g h i j))) GBasically, we apply rest six times before apply first to get the seventh element. In fact, we could have defined the function list-nth (see previous tutorial) in the following way:
(defun list-nth (N L) (first (repeat-transformation (function rest) N L)))(list-nth numbers the member of a list from zero onwards.)
As you can see, functions that accepts other functions as arguments are very powerful abstractions. You can encapsulate generic algorithms in such a function, and parameterize their behavior by passing in different function arguments. We call a function that has functional parameters (or return a function as its value) a higher-order function.
One last point before we move on. The closure constructor function is used very often when working with higher-order functions. Common LISP therefore provide another equivalent syntax to reduce typing. When we want Common LISP to interpret a name F as a function, instead of typing (function F), we can also type the shorthand #'F. The prefix #' is nothing but an alternative syntax for the closure constructor. For example, we could enter the following:
USER(33): (repeat-transformation #'double 4 1) 16 USER(34): (repeat-transformation #'prepend-blah 10 nil) (BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH) USER(35): (first (repeat-transformation #'rest 6 '(a b c d e f g h i j))) G
Some of the functions, like prepend-blah for example, serves no other purpose but to instantiate the generic algorithm repeat-transformation. It would be tedious if we need to define it as a global function using defun before we pass it into repeat-transformation. Fortunately, LISP provides a mechanism to help us define functions "in place":
USER(36): (repeat-transformation #'(lambda (L) (cons 'blah L)) 10 nil) (BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH BLAH)The first argument (lambda (L) (cons 'blah L)) is a lambda expression. It designates an anonymous function (nameless function) with one parameter L, and it returns as a function value (cons 'blah L). We prefix the lambda expression with the closure constructor #' since we want Common LISP to interpret the argument as a function rather than a call to a function named lambda.
Similarly, we could have computed powers as follows:
USER(36): (repeat-transformation #'(lambda (x) (* 2 x)) 4 1) 16
(apply-func-list (list #'double #'list-length #'rest) '(1 2 3))is equivalent to
(double (list-length (rest '(1 2 3))))
We have seen how we could iterate through a list using linear recursion. We have also seen how such recursion can be optimized if structured in a tail-recursive form. However, many of the the list processing functions look striking similar. Consider the following examples:
(defun double-list-elements (L)
"Given a list L of numbers, return a list containing the elements of L multiplied by 2."
(if (null L)
nil
(cons (double (first L)) (double-list-elements (rest L)))))
(defun reverse-list-elements (L)
"Given a list L of lists, return a list containing the reversal of L's members."
(if (null L)
nil
(cons (reverse (first L)) (reverse-list-elements (rest L)))))
We could come up with infinitely many more examples of this sort.
Having to write a new function everytime we want to iterate
through a list is both time-consuming and error-prone.
The solution is to capture the generic logic of list iteration
in higher-order functions, and specialize their behaviors by
passing in functional arguments.
If we look at the definitions of double-list-elements and reverse-list-elements, we see that they apply a certain function to the first element of their input, then recursively invoke themselves to process the rest of the input list, and lastly combine the result of the two function calls using cons. We could capture this logic into the following function:
(defun mapfirst (F L)
"Apply function F to every element of list L, and return a list containing the results."
(if (null L)
nil
(cons (funcall F (first L)) (mapfirst F (rest L)))))
The functions double-list-elements and reverse-list-elements can be replaced by the following:
USER(18): (mapfirst #'double '(1 2 3 4)) (2 4 6 8) USER(19): (mapfirst #'reverse '((1 2 3) (a b c) (4 5 6) (d e f))) ((3 2 1) (C B A) (6 5 4) (F E D))
Of course, you could also pass lambda abstractions as arguments:
USER(20): (mapfirst #'(lambda (x) (* x x)) '(1 2 3 4)) (1 4 9 16)
In fact, the higher-order function is so useful that Common LISP defines a function mapcar that does exactly what mapfirst is intended for:
USER(22): (mapcar #'butlast '((1 2 3) (a b c) (4 5 6) (d e f))) ((1 2) (A B) (4 5) (D E))The reason why it is called mapcar is that the function first was called car in some older dialects of LISP (and rest was called cdr in those dialects; Common LISP still supports car and cdr but we strongly advice you to stick with the more readable first and rest). We suggest you to consider using mapcar whenever you are tempted to write your own list-iterating functions.
The function mapcar is an example of generic iterators, which capture the generic logic of iterating through a list. If we look at what we do the most when we iterate through a list, we find that the following kinds of iterations occurs most frequently in our LISP programs:
Let us begin by writing a function that returns an even element in a list of numbers:
(defun find-even (L)
"Given a list L of numbers, return the leftmost even member."
(if (null L)
nil
(if (evenp (first L))
(first L)
(find-even (rest L)))))
We notice that the essential logic of searching can be extracted out into the following definition:
(defun list-find-if (P L)
"Find the leftmost element of list L that satisfies predicate P."
(if (null L)
nil
(if (funcall P (first L))
(first L)
(list-find-if P (rest L)))))
The function list-find-if examines the elements of L
one by one, and return the first one that satisfies predicate P.
The function can be used for locating even or non-nil members
in a list:
USER(34): (list-find-if #'evenp '(1 3 5 8 11 12)) 8 USER(35): (list-find-if #'(lambda (X) (not (null X))) '(nil nil (1 2 3) (4 5))) (1 2 3)
Common LISP defines a built-in function find-if which is a more general version of list-find-if. It can be used just like list-find-if:
USER(37): (find-if #'evenp '(1 3 5 8 11 12)) 8 USER(38): (find-if #'(lambda (X) (not (null X))) '(nil nil (1 2 3) (4 5))) (1 2 3)
Given a list of lists, suppose we want to screen out all the member lists with length less than three. We could do so by the following function:
(defun remove-short-lists (L)
"Remove all members of L that has length less than three."
(if (null L)
nil
(if (< (list-length (first L)) 3)
(remove-short-lists (rest L))
(cons (first L) (remove-short-lists (rest L))))))
To articulate the correctness of this implementation, consider the
following. The list L is either nil or constructed
by cons.
USER(17): (remove-short-lists '((1 2 3) (1 2) nil (1 2 3 4)))
0: (REMOVE-SHORT-LISTS ((1 2 3) (1 2) NIL (1 2 3 4)))
1: (REMOVE-SHORT-LISTS ((1 2) NIL (1 2 3 4)))
2: (REMOVE-SHORT-LISTS (NIL (1 2 3 4)))
3: (REMOVE-SHORT-LISTS ((1 2 3 4)))
4: (REMOVE-SHORT-LISTS NIL)
4: returned NIL
3: returned ((1 2 3 4))
2: returned ((1 2 3 4))
1: returned ((1 2 3 4))
0: returned ((1 2 3) (1 2 3 4))
((1 2 3) (1 2 3 4))
Alternatively, we could have removed short lists using Common LISP's built-in function remove-if:
USER(19): (remove-if #'(lambda (X) (< (list-length X) 3)) '((1 2 3) (1 2) nil (1 2 3 4))) ((1 2 3) (1 2 3 4))
The function (remove-if P L) constructs a new version of list L that contains only members not satisfying predicate P. For example, we can remove all even members from the list (3 6 8 9 10 13 15 18) by the following:
USER(21): (remove-if #'(lambda (X) (zerop (rem x 2))) '(3 6 8 9 10 13 15 18)) (3 9 13 15)Without remove-if, we would end up having to implement a function like the following:
(defun remove-even (L)
"Remove all members of L that is an even number."
(if (null L)
nil
(if (zerop (rem (first L) 2))
(remove-even (rest L))
(cons (first L) (remove-even (rest L))))))
We could actually implement list-intersection using remove-if and lambda abstraction:
(defun list-intersection (L1 L2) "Compute the intersection of lists L1 and L2." (remove-if #'(lambda (X) (not (member X L2))) L1))In the definition above, the lambda abstraction evaluates to a predicate that returns true if its argument is not a member of L2. Therefore, the remove-if expression removes all elements of L1 that is not a member of L2. This precisely gives us the intersection of L1 and L2.
The functions we have seen so far return a single value, but some LISP functions return two or more values. For example, if two arguments number and divisor are passed to the floor function, it returns two values, the quotient q and the remainder r so that number = divisor * q + r.
USER(11): (floor 17 5) 3 2 USER(12): (floor -17 5) -4 3Regular binding constructs like let and let* only allows us to catch the first returned value of a multiple-valued function, as the following example illustrates:
USER(13): (let ((x (floor 17 5))) x) 3One can use the multiple-value-bind to receive the results of a multiple-valued function:
USER(14): (multiple-value-bind (x y) (floor 17 5)
(+ x y))
5
In the above expression, (x y) is the list of variables
binding to the returned values, (floor 17 5) is the
expression generating multiple results. Binding the two values
of (floor 17 5) to x and y, LISP
then evaluates the expression (+ x y).
One may also write LISP functions that return multiple values:
(defun order (a b)
"Return two values: (min a b) and (max a b)."
(if (>= a b)
(values b a)
(values a b)))
The values special form returns its arguments as multiple
values.
For more information about LISP constructs for handling multiple values, consult section 7.10 of CLTL2.