**Common Lisp the Language, 2nd Edition**

The following functions perform various operations on lists.

The list is one of the original Lisp data types. The very name ``Lisp''
is an abbreviation for ``LISt Processing.''

**[Function]**

`endp object`

The predicate `endp` is the recommended way to test for the end
of a list. It is false of conses, true of `nil`, and an error for
all other arguments.

**[Function]**

`list-length list`

`list-length` returns, as an integer, the length of *list*.
`list-length` differs from `length` when the *list* is
circular; `length` may fail to return, whereas `list-length`
will return `nil`.
For example:

(list-length '()) => 0 (list-length '(a b c d)) => 4 (list-length '(a (b c) d)) => 3 (let ((x (list 'a b c))) (rplacd (last x) x) (list-length x)) =>nil

`list-length` could be implemented as follows:

(defun list-length (x) (do ((n 0 (+ n 2)) ;Counter (fast x (cddr fast)) ;Fast pointer: leaps by 2 (slow x (cdr slow))) ;Slow pointer: leaps by 1 (nil) ;; If fast pointer hits the end, return the count. (when (endp fast) (return n)) (when (endp (cdr fast)) (return (+ n 1))) ;; If fast pointer eventually equals slow pointer, ;; then we must be stuck in a circular list. ;; (A deeper property is the converse: if we are ;; stuck in a circular list, then eventually the ;; fast pointer will equal the slow pointer. ;; That fact justifies this implementation.) (when (and (eq fast slow) (> n 0)) (return nil))))

See `length`, which will return the length of any sequence.

**[Function]**

`nth n list`

`(nth n list)` returns the

(nth 0 '(foo bar gack)) => foo (nth 1 '(foo bar gack)) => bar (nth 3 '(foo bar gack)) =>()

`nth` may be used to specify a *place* to `setf`;
when `nth` is used in this way, the argument *n* must be less
than the length of the *list*.

Note that the arguments to `nth` are reversed from the order
used by most other sequence selector functions such as `elt`.

**[Function]**

`first list `

These functions are sometimes convenient for accessing particular
elements of a list. `first` is the same as `car`,
`second` is the same as `cadr`, `third` is the
same as `caddr`, and so on.
Note that the ordinal numbering used here is one-origin,
as opposed to the zero-origin numbering used by `nth`:

(fifth x) == (nth 4 x)

`setf` may be used with each of these functions to store
into the indicated position of a list.

**[Function]**

`rest list`

`rest` means the same as `cdr` but mnemonically complements `first`.
`setf` may be used with `rest` to replace the *cdr* of a list
with a new value.

**[Function]**

`nthcdr n list`

`(nthcdr n list)` performs the

(nthcdr 0 '(a b c)) => (a b c) (nthcdr 2 '(a b c)) => (c) (nthcdr 4 '(a b c)) =>()

In other words, it returns the *n*th *cdr* of the list.

(car (nthcdr n x)) == (nth n x)

X3J13 voted in January 1989
(ARGUMENTS-UNDERSPECIFIED)
to clarify that the argument *n*
must be a non-negative integer.

**[Function]**

`last list`

`last` returns the last cons (*not* the last element!) of *list*.
If *list* is `()`, it returns `()`.
For example:

(setq x '(a b c d)) (last x) => (d) (rplacd (last x) '(e f)) x => '(a b c d e f) (last '(a b c . d)) => (c . d)

X3J13 voted in June 1988
(LAST-N)
to extend the `last` function to accept
an optional second argument. The effect is to make `last`
complementary in operation to `butlast`.
The new description (with some additional examples) would be as follows.

**[Function]**

`last list &optional (n 1)`

`last` returns the tail of the *list*
consisting of the last *n* conses of *list*. The *list* may
be a dotted list. It is an error if the *list* is circular.

The argument *n* must be a non-negative integer.
If *n* is zero, then the atom that terminates the *list*
is returned. If *n* is not less than the number of cons cells
making up the *list*, then the *list* itself is returned.

For example:

(setq x '(a b c d)) (last x) => (d) (rplacd (last x) '(e f)) x => '(a b c d e f) (last x 3) => (d e f) (last '()) => () (last '(a b c . d)) => (c . d) (last '(a b c . d) 0) => d (last '(a b c . d) 2) => (b c . d) (last '(a b c . d) 1729) => (a b c . d)

**[Function]**

`list &rest args`

`list` constructs and returns a list of its arguments.
For example:

(list 3 4 'a (car '(b . c)) (+ 6 -2)) => (3 4 a b 4)

(list) => () (list (list 'a 'b) (list 'c 'd 'e)) => ((a b) (c d e))

**[Function]**

`list* arg &rest others`

`list*` is like `list` except that the last *cons*
of the constructed list is ``dotted.'' The last argument to `list*`
is used as the *cdr* of the last cons constructed;
this need not be an atom. If it is not an atom,
then the effect is to add several new elements to the front of a list.
For example:

(list* 'a 'b 'c 'd) => (a b c . d)

This is like

(cons 'a (cons 'b (cons 'c 'd)))

Also:

(list* 'a 'b 'c '(d e f)) => (a b c d e f) (list* x) == x

**[Function]**

`make-list size &key :initial-element`

This creates and returns a list containing *size* elements, each
of which is initialized to the `:initial-element`
argument (which defaults to `nil`).
*size* should be a non-negative integer.
For example:

(make-list 5) => (nil nil nil nil nil) (make-list 3:initial-element'rah) => (rah rah rah)

**[Function]**

`append &rest lists`

The arguments to `append` are lists. The result is a list that is the
concatenation of the arguments.
The arguments are not destroyed.
For example:

(append '(a b c) '(d e f) '()'(g)) => (a b c d e f g)

Note that `append` copies the top-level list structure of each of its
arguments *except* the last.
The function `concatenate` can perform a similar operation, but always
copies all its arguments. See also `nconc`, which is like `append`
but destroys all arguments but the last.

The last argument actually need not be a list but may be any Lisp object,
which becomes the tail end of the constructed list.
For example, `(append '(a b c) 'd)` => `(a b c . d)`.

`(append x '())` is an idiom once frequently used to copy the
list

**[Function]**

`copy-list list`

This returns a list that is `equal` to *list*, but not `eq`.
Only the top level of list structure is copied; that is, `copy-list`
copies in the *cdr* direction but not in the *car* direction.
If the list is ``dotted,'' that is, `(cdr (last list))`
is a non-

**[Function]**

`copy-alist list`

`copy-alist` is for copying association lists. The top level of
list structure of *list* is copied, just as for `copy-list`.
In addition, each element of *list* that is a cons is replaced
in the copy by a new cons with the same *car* and *cdr*.

**[Function]**

`copy-tree object`

`copy-tree` is for copying trees of conses.
The argument *object* may be any Lisp object.
If it is not a cons, it is returned; otherwise
the result is a new cons of the results of calling `copy-tree`
on the *car* and *cdr* of the argument. In other words,
all conses in the tree are copied recursively, stopping
only when non-conses are encountered.
Circularities and the sharing of substructure are *not* preserved.

**[Function]**

`revappend x y`

`(revappend x y)` is exactly the same as

**[Function]**

`nconc &rest lists`

`nconc` takes lists as arguments. It returns a list that is the arguments
concatenated together. The arguments are changed rather than copied.
(Compare this with `append`, which copies arguments rather than
destroying them.)
For example:

(setq x '(a b c)) (setq y '(d e f)) (nconc x y) => (a b c d e f) x => (a b c d e f)

Note, in the example, that the value of `x` is now different,
since its last cons has been `rplacd`'d to the value of `y`.
If one were then to evaluate `(nconc x y)` again,
it would yield a piece of ``circular'' list
structure, whose printed representation would be
`(a b c d e f d e f d e f ...)`, repeating forever;
if the `*print-circle*` switch were non-`nil`,
it would be printed as `(a b c . #1=(d e f . #1#))`.

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)
to clarify the permissible side effects of certain operations.
The side-effect behavior of `nconc` is specified by a recursive relationship
outlined in the following table, in which a call to `nconc` matching
the earliest possible
pattern on the left is required to have side-effect behavior
equivalent to the corresponding expression on the right.

(nconc) nil ;No side effects (nconc nil .r) (nconc .r) (nconcx)x(nconcxy) (let ((px) (qy)) (rplacd (last p) q) p) (nconcxy.r) (nconc (nconcxy) .r)

**[Function]**

`nreconc x y`

`(nreconc x y)` is exactly the same as

(setq planets '(jupiter mars earth venus mercury)) (setq more-planets '(saturn uranus pluto neptune)) (nreconc more-planets planets) => (neptune pluto uranus saturn jupiter mars earth venus mercury) and now the value ofmore-planetsis not well defined

X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)
to clarify the permissible side effects of certain operations;
`(nreconc x y)` is permitted and
required to have side-effect behavior
equivalent to that of

**[Macro]**

`push item place`

The form *place* should be the name of a generalized variable
containing a list; *item* may refer to any Lisp object. The *item*
is consed onto the front of the list, and the augmented list is stored
back into *place* and returned.
The form *place* may be any form acceptable as a
generalized variable to `setf`. If the list held in *place* is
viewed as a push-down stack, then `push` pushes an element onto the top
of the stack.
For example:

(setq x '(a (b c) d)) (push 5 (cadr x)) => (5 b c) and now x => (a (5 b c) d)

The effect of `(push item place)`
is roughly equivalent to

(setfplace(consitemplace))

except that the latter would evaluate any subforms of *place*
twice, while `push` takes care to evaluate them only once.
Moreover, for certain *place* forms `push` may be
significantly more efficient than the `setf` version.

X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER)
to clarify order of evaluation (see section 7.2).
Note that *item* is fully evaluated before any part of *place*
is evaluated.

**[Macro]**

`pushnew item place &key :test :test-not :key`

The form *place* should be the name of a generalized variable
containing a list; *item* may refer to any Lisp object. If the
*item* is not already a member of the list (as determined by
comparisons using the `:test` predicate, which defaults to `eql`),
then the *item* is consed onto the front of the list, and
the augmented list is stored back into *place* and returned; otherwise
the unaugmented list is returned. The form *place* may be
any form acceptable as a generalized variable to `setf`. If the
list held in *place* is viewed as a set, then `pushnew` adjoins an
element to the set; see `adjoin`.

The keyword arguments to `pushnew`
follow the conventions for the generic sequence
functions. See chapter 14.
In effect, these keywords are simply passed on to the `adjoin` function.

`pushnew` returns the new contents of the *place*.
For example:

(setq x '(a (b c) d)) (pushnew 5 (cadr x)) => (5 b c) and now x => (a (5 b c) d) (pushnew 'b (cadr x)) => (5 b c) andxis unchanged

The effect of

(pushnewitemplace:testp)

is roughly equivalent to

(setfplace(adjoinitemplace:testp))

except that the latter would evaluate any subforms of
*place* twice, while `pushnew` takes care to evaluate them only once.
Moreover, for certain *place* forms `pushnew` may be
significantly more efficient than the `setf` version.

X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER)
to clarify order of evaluation (see section 7.2).
Note that *item* is fully evaluated before any part of *place*
is evaluated.

**[Macro]**

`pop place`

The form *place* should be the name of a generalized variable
containing a list. The result of `pop` is the `car` of the contents
of *place*, and as a side effect the `cdr` of the contents is stored
back into *place*. The form *place* may be any form acceptable as a
generalized variable to `setf`. If the list held in *place* is
viewed as a push-down stack, then `pop` pops an element from the top of
the stack and returns it.
For example:

(setq stack '(a b c)) (pop stack) => a and now stack => (b c)

The effect of `(pop place)` is roughly equivalent to

(prog1 (carplace) (setfplace(cdrplace)))

except that the latter would evaluate any subforms of *place*
three times, while `pop` takes care to evaluate them only once.
Moreover, for certain *place* forms `pop` may be
significantly more efficient than the `setf` version.

X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER)
to clarify order of evaluation (see section 7.2).

**[Function]**

`butlast list &optional n`

This creates and returns a list with the same elements as *list*,
excepting the last *n* elements.
*n* defaults to 1. The argument is not destroyed.
If the *list* has fewer than *n* elements, then `()` is returned.
For example:

(butlast '(a b c d)) => (a b c) (butlast '((a b) (c d))) => ((a b)) (butlast '(a)) =>()(butlast nil) =>()

The name is from the phrase ``all elements but the last.''

**[Function]**

`nbutlast list &optional n`

This is the destructive version of `butlast`; it changes the *cdr* of
the cons *n*+1 from the end of the *list* to `nil`. *n* defaults to 1.
If the *list* has fewer than *n* elements, then `nbutlast`
returns `()`, and the argument is not modified. (Therefore
one normally writes `(setq a (nbutlast a))` rather than simply
`(nbutlast a)`.)
For example:

(setq foo '(a b c d)) (nbutlast foo) => (a b c) foo => (a b c) (nbutlast '(a)) =>()(nbutlast 'nil) =>()

**[Function]**

`ldiff list sublist`

*list* should be a list, and *sublist* should be a sublist
of *list*, that is, one of the conses that make up *list*.
`ldiff` (meaning ``list difference'') will return a new (freshly consed)
list, whose elements are those elements of *list* that appear before
*sublist*. If *sublist* is not a tail of *list*
(and in particular if *sublist* is `nil`),
then a copy of the entire *list* is returned.
The argument *list* is not destroyed.
For example:

(setq x '(a b c d e)) (setq y (cdddr x)) => (d e) (ldiff x y) => (a b c) but (ldiff '(a b c d) '(c d)) => (a b c d)

since the sublist was not `eq` to any part of the list.

AI.Repository@cs.cmu.edu