Next: Alteration of List Up: Lists Previous: Conses
Common Lisp the Language, 2nd Edition
Next: Alteration of List
Up: Lists
Previous: Conses
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]
endpobject
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-lengthlist
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)) => nillist-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]
nthnlist
(nthnlist)
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]
firstlist
secondlist
thirdlist
fourthlist
fifthlist
sixthlist
seventhlist
eighthlist
ninthlist
tenthlist
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]
restlist
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]
nthcdrnlist
(nthcdrnlist)
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)
X3J13 voted in January 1989 (ARGUMENTS-UNDERSPECIFIED) to clarify that
the argument n must be a non-negative integer.
[Function]
lastlist
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]
lastlist&optional (n1)
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 &restargs
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&restothers
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-listsize&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 &restlists
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).
(appendx'``()``) is
an idiom once frequently used to copy the list x, but the
copy-list function is more appropriate to this task.
[Function]
copy-listlist
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 (lastlist)) is a
non-nil atom, this will be true of the returned list also.
See also copy-seq and copy-tree.
[Function]
copy-alistlist
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-treeobject
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]
revappendxy
(revappendxy)
is exactly the same as
(append (reversex)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 &restlists
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)
(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)[Function]
nreconcxy
(nreconcxy)
is exactly the same as
(nconc (nreversex)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
X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED) to clarify
the permissible side effects of certain operations;
(nreconcxy)
is permitted and required to have side-effect behavior equivalent to
that of
(nconc (nreversex)y).
[Macro]
pushitemplace
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
(pushitemplace)
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.
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]
pushnewitemplace&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 unchangedThe 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.
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]
popplace
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
(popplace) 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.
X3J13 voted in March 1988 (PUSH-EVALUATION-ORDER) to clarify order of
evaluation (see section 7.2).
[Function]
butlastlist&optionaln
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]
nbutlastlist&optionaln
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]
ldifflistsublist
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: Alteration of List
Up: Lists
Previous: Conses
AI.Repository@cs.cmu.edu