# Advanced Functional Programming in LISP

# Auxiliary Functions and Accumulator Variables

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 x_{1} x_{2} ... x_{n})` is just a shorthand for

`(cons`. So, the expression

*x*(cons_{1}*x*... (cons_{2}*x*nil) ... ))_{n}`(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`:

**Case 1:***L*is`nil`.

The reversal of*L*is simply`nil`.**Case 2:***L*is constructed from a call to`cons`.

Then`L`has two components:`(first`and*L*)`(rest`. If we append*L*)`(first`to the end of the reversal of*L*)`(rest`, then we obtain the reversal of*L*)*L*. Of course, we could make use of`list-append`to do this. However,`list-append`expects two list arguments, so we need to construct a singleton list containing`(first`before we pass it as a second argument to*L*)`list-append`.

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(N ^{2})*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`:

**Case 1:***L*is`nil`.

The reversal of*L*is simply`nil`. The result of appending*A*to the end of an empty list is simply*A*itself.**Case 2:***L*is constructed by`cons`.

Now*L*is composed of two parts:`(first`and*L*)`(rest`. Observe that*L*)`(first`is the last element in the reversal of*L*)*L*. If we are to append*A*to the end of the reversal of*L*, then`(first`will come immediately before the elements of*L*)*A*. Observing the above, we recognize that we obtain the desired result by recursively appending`(cons (first`to the reversal of*L*)*A*)`(rest`.*L*)

Tracing both `list-reverse` and `list-reverse-aux`, we get the following:

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*.

## Factorial Revisited

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`indeed returns the product of

*N**A*)*N!*and

*A*) can be established as follows.

*N*is either one or larger than one.

*Case 1*:*N = 1*

The product of*A*and*1!*is simply*A * 1! = A*.*Case 2*:*N > 1*

Since*N! = N * (N-1)!*, we then have*N! * A = (N-1)! * (N * A)*, thus justifying our implementation.

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:

- An auxiliary function generalizes the functionality of the driver function by promising to compute the function of interest and also combine the result with the value of the accumulator variable. In the case of
`list-reverse-aux`, our original interest were computing list reversals, but then the auxiliary function computes a more general concept, namely, that of appending an auxiliary list to some list reversal. In the case of`fast-factorial-aux`, our original interest were computing factorials, but the auxiliary function computes a more general value, namely, the product of some auxiliary number with a factorial. - At each level of recursion, the auxiliary function reduces the problem into a smaller subproblem, and accumulating intermediate results in the accumulator variable. In the case of
`list-reverse-aux`, recursion is applied to the sublist`(rest`, while*L*)`(first`is*L*)`cons`‘ed with*A*. In the case of`fast-factorial`, recursion is applied to*(N – 1)!*, while*N*is multiplied with*A*. - The driver function initiates the recursion by providing an initial value for the auxiliary variable. In the case of computing list reversals,
`list-reverse`initializes*A*to`nil`. In the case of computing factorials,`fast-factorial`initializes*A*to 1.

Now that you understand how `fast-factorial` works, we explain where the adjective “fast” come from …

## Tail Recursions

Recursive functions are usually easier to reason about. Notice how we articulate the correctness of recursive functions in this and the previous tutorial. However, some naive programmers complain that recursive functions are slow when compared to their iterative counter parts. For example, consider the original implementation of `factorial`we saw in the previous tutorial:

(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.

**Exercise:** Recall that the *N*‘th *triangular number* is defined to be *1 + 2 + 3 + … + N*. Give a tail-recursive implementation of the function `(fast-triangular N)` which returns the

*N*‘th triangular number.

**Exercise:** Give a tail-recursive implementation of the function `(fast-power B E)` that raises

*B*to the power

*E*(assuming that both

*B*and

*E*are non-negative integers).

**Exercise:** Give a tail-recursive implementation of the function `(fast-list-length L)`, which returns the length of a given list

*L*.

## Functions as First-Class Objects

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 2^{4} by applying the `double`transformation 4 times on 1:

USER(10): (double (double (double (double 1)))) 16

Not 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

*X*

_{1}*X*…

_{2}*X*, the form

_{n}`(funcall`invoke the function

*F**X*_{1}*X*..._{2}*X*)_{n}*F*with arguments

*X*,

_{1}*X*, …,

_{2}*X*. The variable

_{n}*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) 16

There 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

## Higher-Order Functions

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))) G

Basically, 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

## Lambda Expressions

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

**Exercise**: Define a function `(apply-func-list L X)` so that, given a list

*L*of functions and an object

*X*,

`apply-func-list`applies the functions in

*L*to

*X*in reversed order. For example, the following expression

(apply-func-list (list #'double #'list-length #'rest) '(1 2 3))

is equivalent to

(double (list-length (rest '(1 2 3))))

**Exercise**: Use `apply-func-list`to compute the following:

- 10 times the fourth element of the list
`(10 20 30 40 50)`, - the third element of the second element in the list
`((1 2) (3 4 5) (6))`, - the difference between 10 and the length of
`(a b c d e f)`, - a list containing a list containing the symbol
`blah`.

## Iterating Through a List

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:

*Transformation iteration*: transforming a list by systematically applying a monadic function to the elements of the list.*Search iteration*: searching for a list member that satisfies a given condition.*Filter iteration*: screening out all members that does not satisfy a given condition.

As we have already seen, `mapcar` implements the generic algorithm for performing transformation iteration. In the following, we will look at the analogous of `mapcar`for the remaining iteration categories.

## Search Iteration

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)))))

**Exercise:** Implement a function that, when given a list *L* of lists, return a non-empty member of *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)

**Exercise**: Use `find-if` to define a function that searches among a list of lists for a member that has length at least 3.

**Exercise**: Use `find-if` to define a function that searches among a list of lists for a member that contains an even number of elements.

**Exercise**: Use `find-if` to define a function that searches among a list of numbers for a member that is divisible by three.

## Filter Iteration

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`.

*Case 1*:*L*is`nil`.

Removing short lists from an empty list simply results in an empty list.*Case 2*:*L*is constructed by`cons`.

*L*has two components:`(first`and*L*)`(rest`. We have two cases: either*L*)`(first`has fewer than 3 members or it has at least 3 members.*L*)*Case 2.1*:`(first`has fewer than three elements.*L*)

Since`(first`is short, and will not appear in the result of removing short lists from*L*)*L*, the latter is equivalent to the result of removing short lists from`(rest`.*L*)*Case 2.2*:`(first`has at least three elements.*L*)

Since`(first`is not short, and will appear in the result of removing short lists from*L*)*L*, the latter is equivalent to adding`(first`to the result of removing short lists from*L*)`(rest`.*L*)

A typical execution trace is the following:

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))))))

**Exercise**: Demonstrate the correctness of `remove-even` using arguments you have seen in this tutorial.

**Exercise**: Observe the recurring pattern in `remove-short-lists` and `remove-even`, and implement your own version of `remove-if`.

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*.

**Exercise**: Use `remove-if` and lambda abstractions to implement `list-difference`.

**Exercise**: Look up the functionality of `remove-if-not` in CTRL2. Re-implement `list-intersection` using `remove-if-not` and lambda abstraction.

## Functions Returning Multiple Values

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 3

Regular 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) 3

One 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.

**Exercise:** Implement a tail-recursive function `(list-min-max L)` that returns two values: the minimum and maximum members of a list

*L*of numbers.

Posted on April 21, 2012, in lisp and tagged common lisp, programming, technology. Bookmark the permalink. Leave a comment.

## Leave a comment

## Comments 0