Common Lisp the Language, 2nd Edition

next up previous contents index
Next: Alteration of List Up: Lists Previous: Conses

15.2. Lists

The following functions perform various operations on lists.

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


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

Implementation note: Implementations are encouraged to signal an error, especially in the interpreter, for a non-list argument. The endp function is defined so as to allow compiled code to perform simply an atom check or a null check if speed is more important than safety.


[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 element of list, where the car of the list is the ``zeroth'' element. The argument n must be a non-negative integer. If the length of the list is not greater than n, then the result is (), that is, nil. (This is consistent with the idea that the car and cdr of () are each ().) For example: 

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

Compatibility note: This is not the same as the Interlisp function called nth, which is similar to but not exactly the same as the Common Lisp function nthcdr. This definition of nth is compatible with Lisp Machine Lisp and NIL (New Implementation of Lisp). Also, some people have used macros and functions called nth of their own in their old MacLisp programs, which may not work the same way.

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
second list
third list
fourth list
fifth list
sixth list
seventh list
eighth list
ninth list
tenth 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 cdr operation n times on list, and returns the result. For example: 

(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 nth cdr of the list.

Compatibility note: This is similar to the Interlisp function nth, except that the Interlisp function is one-based instead of zero-based. 

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

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

old_change_begin

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


old_change_end

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


change_end


[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 x, but the copy-list function is more appropriate to this task.


[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-nil atom, this will be true of the returned list also. See also copy-seq and copy-tree.


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

Compatibility note: This function is called copy in Interlisp.


[Function]
revappend x y

(revappend x y) is exactly the same as (append (reverse x) y) except that it is potentially more efficient. Both x and y should be lists. The argument x is copied, not destroyed. Compare this with nreconc, which destroys its first argument.


[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#)).

change_begin
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) 
(nconc x)               x 
(nconc x y)             (let ((p x) (q y)) 
                          (rplacd (last p) q) 
                          p) 
(nconc x y . r)         (nconc (nconc x y) . r)


change_end


[Function]
nreconc x y

(nreconc x y) is exactly the same as (nconc (nreverse x) y) except that it is potentially more efficient. Both x and y should be lists. The argument x is destroyed. Compare this with revappend. 

(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 of more-planets is not well defined

change_begin
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 (nconc (nreverse x) y).
change_end


[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 

(setf place (cons item place))

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.

change_begin
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.
change_end


[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)  and x is unchanged

The effect of 

(pushnew item place :test p)

is roughly equivalent to 

(setf place (adjoin item place :test p))

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.

change_begin
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.
change_end


[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 (car place) (setf place (cdr place)))

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.

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


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


next up previous contents index
Next: Alteration of List Up: Lists Previous: Conses

AI.Repository@cs.cmu.edu