Programming Language - Common Lisp 14. Conses

Version 15.17, X3J13/94-101. Version 15.17, X3J13/94-101.
Wed 11-May-1994 6:57pm EDT Wed 11-May-1994 6:57pm EDT
Programming Language|Common Lisp
14. Conses
Conses i ii Programming Language|Common Lisp

14.1 Cons Concepts 14.1.2 Conses as Lists
A cons is a compound data object having two components called the car and the cdr . A list is a chain of conses in which the car of each cons is an element of the list , and the cdr of
each cons is either the next link in the chain or a terminating atom .
car cons rplacd
cdr rplaca A proper list is a list terminated by the empty list . The empty list is a proper list , but is not a
cons .
Figure 14{1. Some dened names relating to conses. An improper list is a list that is not a proper list ; that is, it is a circular list or a dotted list .
Depending on context, a group of connected conses can be viewed in a variety of dierent ways. A dotted list is a list that has a terminating atom that is not the empty list . A non-nil atom by
A variety of operations is provided to support each of these various views. itself is not considered to be a list of any kind|not even a dotted list .
A circular list is a chain of conses that has no termination because some cons in the chain is the
14.1.1 Conses as Trees cdr of a later cons .
A tree is a binary recursive data structure made up of conses and atoms : the conses are them- append last nbutlast rest
selves also trees (sometimes called \subtrees" or \branches"), and the atoms are terminal nodes butlast ldi nconc revappend
(sometimes called leaves ). Typically, the leaves represent data while the branches establish some copy-alist list ninth second
relationship among that data. copy-list list* nreconc seventh
eighth list-length nth sixth
caaaar caddar cdar nsubst endp make-list nthcdr tailp
caaadr cadddr cddaar nsubst-if fth member pop tenth
caaar caddr cddadr nsubst-if-not rst member-if push third
caadar cadr cddar nthcdr fourth member-if-not pushnew
caaddr cdaaar cdddar sublis
caadr cdaadr cddddr subst Figure 14{3. Some dened names relating to lists.
caar cdaar cdddr subst-if
cadaar cdadar cddr subst-if-not
cadadr cdaddr copy-tree tree-equal
cadar cdadr nsublis 14.1.2.1 Lists as Association Lists
Figure 14{2. Some dened names relating to trees. An association list is a list of conses representing an association of keys with values , where the
car of each cons is the key and the cdr is the value associated with that key .
acons assoc-if pairlis rassoc-if
14.1.1.1 General Restrictions on Parameters that must be Trees assoc assoc-if-not rassoc rassoc-if-not
Except as explicitly stated otherwise, for any standardized function that takes a parameter that is Figure 14{4. Some dened names related to assocation lists.
required to be a tree , the consequences are undened if that tree is circular.
Conses 14{1 14{2 Programming Language|Common Lisp

14.1.2.2 Lists as Sets list System Class

Lists are sometimes viewed as sets by considering their elements unordered and by assuming
there is no duplication of elements. Class Precedence List:
adjoin nset-dierence set-dierence union list, sequence, t
intersection
nintersection
nset-exclusive-or
nunion
set-exclusive-or
subsetp
Description:
A list is a chain of conses in which the car of each cons is an element of the list , and the cdr of
each cons is either the next link in the chain or a terminating atom .
Figure 14{5. Some dened names related to sets.
A proper list is a chain of conses terminated by the empty list, (), which is itself a proper list .
A dotted list is a list which has a terminating atom that is not the empty list . A circular list
is a chain of conses that has no termination because some cons in the chain is the cdr of a later
14.1.2.3 General Restrictions on Parameters that must be Lists cons .
Except as explicitly specied otherwise, any standardized function that takes a parameter that is Dotted lists and circular lists are also lists , but usually the unqualied term \list" within this
required to be a list should be prepared to signal an error of type type-error if the value received specication means proper list . Nevertheless, the type list unambiguously includes dotted lists and
is a dotted list . circular lists .
Except as explicitly specied otherwise, for any standardized function that takes a parameter that For each element of a list there is a cons . The empty list has no elements and is not a cons .
is required to be a list , the consequences are undened if that list is circular .
The types cons and null form an exhaustive partition of the type list.
See Also:
Section 2.4.1 (Left-Parenthesis), Section 22.1.3.5 (Printing Lists and Conses)
null System Class
Class Precedence List:

null, symbol, list, sequence, t
Description:
The only object of type null is nil, which represents the empty list and can also be notated ().
See Also:
Section 2.3.4 (Symbols as Tokens), Section 2.4.1 (Left-Parenthesis), Section 22.1.3.3 (Printing
Symbols)

cons System Class cons Function
Class Precedence List: Syntax:

cons, list, sequence, t cons object-1 object-2 ! cons
Description: Arguments and Values:
A cons is a compound object having two components, called the car and cdr . These form a dotted object-1 |an object .
pair . Each component can be any object .
object-2 |an object .
Compound Type Specier Kind: cons |a cons .
Specializing.
Compound Type Specier Syntax: Description:
Creates a fresh cons , the car of which is object-1 and the cdr of which is object-2 .
(cons [car-typespec [cdr-typespec ]])
Examples:
Compound Type Specier Arguments: (cons 1 2)! (1 . 2)
car-typespec |a type specier , or the symbol *. The default is the symbol *. (cons !
1 nil) (1)
(cons !
nil 2) (NIL . 2)
cdr-typespec |a type specier , or the symbol *. The default is the symbol *. (cons !
nil nil) (NIL)
!
Compound Type Specier Description: (cons
(cons
1 (cons 2 (cons 3 (cons 4 nil))))
!
'a 'b) (A . B)
(1 2 3 4)
This denotes the set of conses whose car is constrained to be of type car-typespec and whose cdr (cons 'a (cons 'b (cons 'c '()))) !(A B C)
is constrained to be of type cdr-typespec . (If either car-typespec or cdr-typespec is *, it is as if the (cons 'a '(b c d)) ! (A B C D)
type t had been denoted.)
See Also:
See Also: list
Section 2.4.1 (Left-Parenthesis), Section 22.1.3.5 (Printing Lists and Conses)
Notes:
If object-2 is a list , cons can be thought of as producing a new list which is like it but has object-
atom Type 1 prepended.
Supertypes: consp Function

atom, t
Description: Syntax:
It is equivalent to (not .
cons) consp object ! generalized-boolean
Arguments and Values:
object |an object .
generalized-boolean|a generalized boolean .

Description: Notes:
Returns true if object is of type cons; otherwise, returns false .
(atom object (typep object 'atom) (not (consp object ))
)
Examples: (not (typep object 'cons)) (typep object '(not cons))
(consp nil) ! false
! true
rplaca, rplacd
(consp (cons 1 2))
The empty list is not a cons , so Function

(consp '()) (consp 'nil) ! false
See Also: Syntax:
rplaca cons object ! cons
listp rplacd cons object ! cons
Notes: Pronunciation:
(consp object ) (typep object 'cons) (not (typep object 'atom)) (typep object '(not
rplaca: [ re plak ] or [ r plak ]
atom)) rplacd: [ re plakd ] or [ r plakd ] or [ re plakde ] or [ r plakde ]
atom Function
cons |a cons .
object |an object .
Syntax: Description:
atom object ! generalized-boolean rplaca replaces the car of the cons with object .
Arguments and Values: rplacd replaces the cdr of the cons with object .
object |an object . Examples:
generalized-boolean|a generalized boolean . (defparameter *some-list* (list* 'one 'two 'three 'four)) ! *some-list*
!
Description: *some-list* (ONE TWO THREE . FOUR)
(rplaca *some-list* 'uno) !
(UNO TWO THREE . FOUR)
Returns true if object is of type atom; otherwise, returns false . *some-list* !(UNO TWO THREE . FOUR)
!
Examples: (rplacd (last *some-list*) (list 'IV))
*some-list* !(UNO TWO THREE IV)
(THREE IV)
(atom 'sss)! true

! false
Side Eects:
(atom
(atom
(cons 1 2))
nil)! true The cons is modied.
(atom '())! true Should signal an error of type type-error if cons is not a cons .
(atom 3) ! true

car, cdr, caar, cadr, cdar, cddr, caaar, caadr, cadar, ::: car, cdr, caar, cadr, cdar, cddr, caaar, caadr, cadar, :::
car, cdr, caar, cadr, cdar, cddr, caaar, caadr, cadar, caddr: [ kad dr ] or [ _ r ]
ka dud
caddr, cdaar, cdadr, cddar, cdddr, caaaar, caaadr, cdr: [ ku_ dr ]
caadar, caaddr, cadaar, cadadr, caddar, cadddr,
cdaaar, cdaadr, cdadar, cdaddr, cddaar, cddadr, cddr: [ kud
_ dr ] or [ _ r ]
k dud
cdddar, cddddr Accessor Arguments and Values:

x |a list .
Syntax: object |an object .
car x ! object (setf (car x) new-object) new-object |an object .
cdr x ! object (setf (cdr x) new-object)
caar x ! object (setf (caar x) new-object) Description:
cadr x ! object (setf (cadr x) new-object) If x is a cons , car returns the car of that cons . If x is nil, car returns nil.
cdar x ! object (setf (cdar x) new-object) If x is a cons , cdr returns the cdr of that cons . If x is nil, cdr returns nil.
cddr x ! object (setf (cddr x) new-object)
caaar x ! object (setf (caaar x) new-object) Functions are provided which perform compositions of up to four car and cdr operations. Their
caadr x ! object (setf (caadr x) new-object) names consist of a C, followed by two, three, or four occurrences of A or D, and nally an R.
cadar x ! object (setf (cadar x) new-object) The series of A's and D's in each function 's name is chosen to identify the series of car and cdr
caddr x ! object (setf (caddr x) new-object) operations that is performed by the function. The order in which the A's and D's appear is the
cdaar x ! object (setf (cdaar x) new-object) inverse of the order in which the corresponding operations are performed. Figure 14{6 denes the
cdadr x ! object (setf (cdadr x) new-object) relationships precisely.
cddar x ! object (setf (cddar x) new-object)
cdddr x ! object (setf (cdddr x) new-object)
caaaar x ! object (setf (caaaar x) new-object)
caaadr x ! object (setf (caaadr x) new-object)
caadar x ! object (setf (caadar x) new-object)
caaddr x ! object (setf (caaddr x) new-object)
cadaar x ! object (setf (cadaar x) new-object)
cadadr x ! object (setf (cadadr x) new-object)
caddar x ! object (setf (caddar x) new-object)
cadddr x ! object (setf (cadddr x) new-object)
cdaaar x ! object (setf (cdaaar x) new-object)
cdaadr x ! object (setf (cdaadr x) new-object)
cdadar x ! object (setf (cdadar x) new-object)
cdaddr x ! object (setf (cdaddr x) new-object)
cddaar x ! object (setf (cddaar x) new-object)
cddadr x ! object (setf (cddadr x) new-object)
cdddar x ! object (setf (cdddar x) new-object)
cddddr x ! object (setf (cddddr x) new-object)
Pronunciation:
cadr: [ ka dr ]

car, cdr, caar, cadr, cdar, cddr, caaar, caadr, cadar, :::
(cadr '(1 2)) !2

This place ::: Is equivalent to this place ::: (car '(a b c)) !A
(caar )x (car (car x )) (cdr '(a b c)) ! (B C)
x x ))
(cadr )
(cdar )x
(car
(cdr
(cdr
(car x )) Exceptional Situations:
(cddr )x (cdr (cdr x )) The functions car and cdr should signal type-error if they receive an argument which is not a
(caaar )x (car (car (car x ))) list . The other functions (caar, cadr, : : : cddddr) should behave for the purpose of error checking
(caadr )x (car (car (cdr x ))) as if dened by appropriate calls to car and cdr.
x x )))
(cadar )
(caddr )x
(car
(car
(cdr
(cdr
(car
(cdr x ))) See Also:
(cdaar )x (cdr (car (car x ))) rplaca, rst, rest
x x )))
(cdadr )
(cddar )x
(cdr
(cdr
(car
(cdr
(cdr
(car x ))) Notes:
(cdddr )x (cdr (cdr (cdr x ))) The car of a cons can also be altered by using rplaca, and the cdr of a cons can be altered by
(caaaar ) x (car (car (car (car x )))) using rplacd.
(caaadr ) x (car (car (car (cdr x )))) x x
(caadar ) x (car (car (cdr (car x )))) (car )
x
(first )
x x
(caaddr ) x (car (car (cdr (cdr x )))) (cadr )
x
(second )
x
(car (cdr ))
x
(cadaar ) x (car (cdr (car (car x )))) (caddr )
x
(third )
x
(car (cdr (cdr )))
x))))
(cadadr ) x (car (cdr (car (cdr x )))) (cadddr ) (fourth ) (car (cdr (cdr (cdr
(caddar ) x (car (cdr (cdr (car x ))))
(cadddr ) x (car (cdr (cdr (cdr x ))))
(cdaaar )
(cdaadr )
(cdadar )
x
x
x
(cdr
(cdr
(cdr
(car
(car
(car
(car
(car
(cdr
(car
(cdr
(car
x ))))
x ))))
x ))))
copy-tree Function
(cdaddr ) x (cdr (car (cdr (cdr x ))))
(cddaar ) x (cdr (cdr (car (car x )))) Syntax:
(cddadr ) x (cdr (cdr (car (cdr x )))) copy-tree tree ! new-tree
(cdddar ) x (cdr (cdr (cdr (car x ))))
(cddddr ) x (cdr (cdr (cdr (cdr x )))) Arguments and Values:
tree |a tree .
Figure 14{6. CAR and CDR variants
new-tree |a tree .
setf can also be used with any of these functions to change an existing component of x , but setf Description:
will not make new components. So, for example, the car of a cons can be assigned with setf of
car, but the car of nil cannot be assigned with setf of car. Similarly, the car of the car of a cons Creates a copy of a tree of conses .
whose car is a cons can be assigned with setf of caar, but neither nilnor a cons whose car is nil If tree is not a cons , it is returned; otherwise, the result is a new cons of the results of calling
can be assigned with setf of caar. copy-tree on the car and cdr of tree . In other words, all conses in the tree represented by tree
The argument x is permitted to be a dotted list or a circular list . are copied recursively, stopping only when non-conses are encountered.
Examples: copy-tree does not preserve circularities and the sharing of substructure.
(car nil) ! NIL
Examples:
(cdr '(1 . 2)) ! 2
(cdr '(1 2)) !(2)
(setq object (list (cons 1 "one")

sublis, nsublis
(cons 2 (list 'a 'b 'c)))) Description:
! ((1 . "one") (2 A B C)) sublis makes substitutions for objects in tree (a structure of conses ). nsublis is like sublis but
(setq object-too object) !((1 . "one") (2 A B C)) destructively modies the relevant parts of the tree .
(setq copy-as-list (copy-list object))
(setq copy-as-alist (copy-alist object)) sublis looks at all subtrees and leaves of tree ; if a subtree or leaf appears as a key in alist (that
(setq copy-as-tree (copy-tree object)) is, the key and the subtree or leaf satisfy the test ), it is replaced by the object with which that
(eq object object-too) ! true key is associated. This operation is non-destructive. In eect, sublis can perform several subst
(eq copy-as-tree object) ! false operations simultaneously.
(eql copy-as-tree object) ! false If sublis succeeds, a new copy of tree is returned in which each occurrence of such a subtree or
(equal copy-as-tree object) ! true leaf is replaced by the object with which it is associated. If no changes are made, the original tree
(setf (first (cdr (second object))) "a"
(car (second object)) "two" is returned. The original tree is left unchanged, but the result tree may share cells with it.
(car object) '(one . 1)) !(ONE . 1)
nsublis is permitted to modify tree but otherwise returns the same values as sublis.
object ! ((ONE . 1) ("two" "a" B C))
object-too
copy-as-list
!
!
((ONE . 1) ("two" "a" B C))
((1 . "one") ("two" "a" B C))
Examples:
copy-as-alist ! ((1 . "one") (2 "a" B C)) (sublis '((x . 100) (z . zprime))
copy-as-tree ! ((1 . "one") (2 A B C)) '(plus x (minus g z x p) 4 . x))
!
See Also: (PLUS 100 (MINUS G ZPRIME 100 P) 4 . 100)
(sublis '(((+ x y) . (- x y)) ((- x y) . (+ x y)))
tree-equal '(* (/ (+ x y) (+ x p)) (- x y))
:test #'equal)
!
sublis, nsublis
(* (/ (- X Y) (+ X P)) (+ X Y))
Function !
(setq tree1 '(1 (1 2) ((1 2 3)) (((1 2 3 4)))))
(1 (1 2) ((1 2 3)) (((1 2 3 4))))
(sublis '((3 . "three")) tree1)
Syntax: ! (1 (1 2) ((1 2 "three")) (((1 2 "three" 4))))
sublis alist tree &key key test test-not ! new-tree (sublis '((t . "string"))
(sublis '((1 . "") (4 . 44)) tree1)
nsublis alist tree &key key test test-not ! new-tree :key #'stringp)
! ("string" ("string" 2) (("string" 2 3)) ((("string" 2 3 44))))
Arguments and Values: tree1 ! (1 (1 2) ((1 2 3)) (((1 2 3 4))))
alist |an association list . (setq tree2 '("one" ("one" "two") (("one" "Two" "three"))))
! ("one" ("one" "two") (("one" "Two" "three")))
tree |a tree . (sublis '(("two" . 2)) tree2)
test |a designator for a function of two arguments that returns a generalized boolean .
! ("one" ("one" "two") (("one" "Two" "three")))
tree2 ! ("one" ("one" "two") (("one" "Two" "three")))
test-not |a designator for a function of two arguments that returns a generalized boolean . !
(sublis '(("two" . 2)) tree2 :test 'equal)
("one" ("one" 2) (("one" "Two" "three")))
key |a designator for a function of one argument, or nil.
(nsublis '((t . 'temp))
new-tree |a tree . tree1
:key #'(lambda (x) (or (atom x) (< (list-length x) 3))))
! ((QUOTE TEMP) (QUOTE TEMP) QUOTE TEMP)

subst, subst-if, subst-if-not, nsubst, nsubst-if, :::
Side Eects: predicate |a symbol that names a function , or a function of one argument that returns a general-
nsublis modies tree . ized boolean value.
See Also: tree |a tree .
subst, Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Side Eects) test |a designator for a function of two arguments that returns a generalized boolean .
Notes: test-not |a designator for a function of two arguments that returns a generalized boolean .
The :test-not parameter is deprecated. key |a designator for a function of one argument, or nil.
Because the side-eecting variants (e.g., nsublis) potentially change the path that is being new-tree |a tree .
traversed, their eects in the presence of shared or circular structure structure may vary in
surprising ways when compared to their non-side-eecting alternatives. To see this, consider the
following side-eect behavior, which might be exhibited by some implementations:
Description:
subst, subst-if , and subst-if-not perform substitution operations on tree . Each function searches
(defun test-it (fn) tree for occurrences of a particular old item of an element or subexpression that satises the test .
(let* ((shared-piece (list 'a 'b))
nsubst, nsubst-if , and nsubst-if-not are like subst, subst-if , and subst-if-not respectively,
(data (list shared-piece shared-piece)))
(funcall fn '((a . b) (b . a)) data)))
except that the original tree is modied.
(test-it #'sublis) !
((B A) (B A)) subst makes a copy of tree , substituting new for every subtree or leaf of tree (whether the subtree
(test-it #'nsublis) !
((A B) (A B)) or leaf is a car or a cdr of its parent) such that old and the subtree or leaf satisfy the test .
nsubst is a destructive version of subst. The list structure of tree is altered by destructively
replacing with new each leaf of the tree such that old and the leaf satisfy the test .
subst, subst-if, subst-if-not, nsubst, nsubst-if, For subst, subst-if , and subst-if-not, if the functions succeed, a new copy of the tree is returned
nsubst-if-not Function in which each occurrence of such an element is replaced by the new element or subexpression. If
no changes are made, the original tree may be returned. The original tree is left unchanged, but
the result tree may share storage with it.
Syntax: For nsubst, nsubst-if , and nsubst-if-not the original tree is modied and returned as the func-
subst new old tree &key key test test-not ! new-tree tion result, but the result may not be eq to tree .
subst-if new predicate tree &key key ! new-tree Examples:
subst-if-not new predicate tree &key key ! new-tree (setq tree1 '(1 (1 2) (1 2 3) (1 2 3 4))) !
(1 (1 2) (1 2 3) (1 2 3 4))
nsubst new old tree &key key test test-not ! new-tree (subst "two" 2 tree1) !(1 (1 "two") (1 "two" 3) (1 "two" 3 4))
(subst "five" 5 tree1) ! (1 (1 2) (1 2 3) (1 2 3 4))
nsubst-if new predicate tree &key key ! new-tree (eq tree1 (subst "five" 5 tree1)) ! implementation-dependent
nsubst-if-not new predicate tree &key key ! new-tree (subst 'tempest 'hurricane
'(shakespeare wrote (the hurricane)))
Arguments and Values: ! (SHAKESPEARE WROTE (THE TEMPEST))

(subst 'foo 'nil '(shakespeare wrote (twelfth night)))
new |an object . ! (SHAKESPEARE WROTE (TWELFTH NIGHT . FOO) . FOO)
old |an object . (subst '(a . cons) '(old . pair)
'((old . spice) ((old . shoes) old . pair) (old . pair))

tree-equal
:test #'equal)
! ((OLD . SPICE) ((OLD . SHOES) A . CONS) (A . CONS))
tree-equal Function
(subst-if 5 #'listp tree1) ! 5 Syntax:

(subst-if-not '(x) #'consp tree1) tree-equal tree-1 tree-2 &key test test-not ! generalized-boolean
! (1 X)
tree1 ! (1 (1 2) (1 2 3) (1 2 3 4)) tree-1 |a tree .
(nsubst 'x 3 tree1 :key #'(lambda (y) (and (listp y) (third y))))
! (1 (1 2) X X) tree-2 |a tree .
tree1 ! (1 (1 2) X X)
Side Eects: test-not |a designator for a function of two arguments that returns a generalized boolean .
nsubst, nsubst-if , and nsubst-if-not might alter the tree structure of tree .
See Also:
substitute, nsubstitute, Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Description:
Side Eects) tree-equal tests whether two trees are of the same shape and have the same leaves. tree-equal
returns true if tree-1 and tree-2 are both atoms and satisfy the test , or if they are both conses
Notes: and the car of tree-1 is tree-equal to the car of tree-2 and the cdr of tree-1 is tree-equal to the
The :test-not parameter is deprecated. cdr of tree-2 . Otherwise, tree-equal returns false .
The functions subst-if-not and nsubst-if-not are deprecated. tree-equal recursively compares conses but not any other objects that have components.
One possible denition of subst: The rst argument to the :test or :test-not function is tree-1 or a car or cdr of tree-1 ; the
(defun subst (old new tree &rest x &key test test-not key)
second argument is tree-2 or a car or cdr of tree-2 .
(cond ((satisfies-the-test old tree :test test
:test-not test-not :key key)
Examples:
new) (setq tree1 '(1 (1 2))
((atom tree) tree) tree2 '(1 (1 2))) !(1 (1 2))
(t (let ((a (apply #'subst old new (car tree) x)) (tree-equal tree1 tree2) ! true
(d (apply #'subst old new (cdr tree) x))) (eql tree1 tree2) ! false
(if (and (eql a (car tree)) (setq tree1 '('a ('b 'c))
(eql d (cdr tree))) tree2 '('a ('b 'c))) !
('a ('b 'c))
tree ! ((QUOTE A) ((QUOTE B) (QUOTE C)))
(cons a d)))))) (tree-equal tree1 tree2 :test 'eq) ! true
Exceptional Situations:
The consequences are undened if both tree-1 and tree-2 are circular.
See Also:
equal, Section 3.6 (Traversal Rules and Side Eects)
Notes:
The :test-not parameter is deprecated.

list, list
list, list Function
copy-list Function Syntax:
list &rest objects ! list
Syntax: list* &rest objects+ ! result
copy-list list ! copy
Arguments and Values: Arguments and Values:
list |a proper list or a dotted list . object |an object .
copy |a list . list |a list .
Description: result |an object .
Returns a copy of list . If list is a dotted list , the resulting list will also be a dotted list . Description:
Only the list structure of list is copied; the elements of the resulting list are the same as the list returns a list containing the supplied objects .
corresponding elements of the given list . list* is like list except that the last argument to list becomes the car of the last cons constructed,
Examples: while the last argument to list* becomes the cdr of the last cons constructed. Hence, any given
call to list* always produces one fewer conses than a call to list with the same number of argu-
(setq lst (list 1 (list 2 3))) !
(1 (2 3))
ments.
(setq slst lst) !(1 (2 3)) If the last argument to list* is a list , the eect is to construct a new list which is similar, but
(setq clst (copy-list lst)) !
(1 (2 3))
which has additional elements added to the front corresponding to the preceding arguments of
(eq slst lst) ! true list*.
(eq clst lst) ! false
(equal clst lst) ! true If list* receives only one object , that object is returned, regardless of whether or not it is a list .
!
Examples:
(rplaca lst "one") ("one" (2 3))
slst ! ("one" (2 3))
clst ! (1 (2 3))
(setf (caadr lst) "two") !
"two" (list 1) ! (1)
lst ! ("one" ("two" 3)) (list* 1) ! 1
slst ! ("one" ("two" 3)) (setq a 1)! 1
clst ! (1 ("two" 3)) (list a 2)! (1 2)
'(a 2) ! (A 2)
Exceptional Situations: (list 'a 2)! (A 2)
The consequences are undened if list is a circular list . (list* a 2)! (1 . 2)
(list) ! i.e.
NIL ; , ()
See Also: !
(setq a '(1 2)) (1 2)
! true
copy-alist, copy-seq, copy-tree (eq a (list* a))
(list 3 4 'a (car '(b . c)) (+ 6 -2)) !
(3 4 A B 4)
Notes:
(list* 'a 'b 'c 'd) (cons 'a (cons 'b (cons 'c 'd)))
!
! (A B C . D)
The copy created is equal to list , but not eq. (list* 'a 'b 'c '(d e f)) (A B C D E F)
See Also:
cons

Notes: (slow x (cdr slow))) ;Slow pointer: leaps by 1.

(nil)
(list* x) x ;; If fast pointer hits the end, return the count.
(when (endp fast) (return n))
(when (endp (cdr fast)) (return (+ n 1)))
list-length
;; If fast pointer eventually equals slow pointer,
Function ;; 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
Syntax: ;; fast pointer will equal the slow pointer.
list-length list ! length ;; That fact justifies this implementation.)

(when (and (eq fast slow) (> n 0)) (return nil))))
list |a proper list or a circular list .
length|a non-negative integer , or nil.
Description: listp Function
Returns the length of list if list is a proper list . Returns nil if list is a circular list .
Examples: Syntax:
listp object ! generalized-boolean
(list-length '(a b c d)) 4 ! Arguments and Values:
(list-length '(a (b c) d)) 3 ! object |an object .
(list-length '()) 0!
(list-length nil) 0! generalized-boolean|a generalized boolean .
(defun circular-list (&rest elements)
(let ((cycle (copy-list elements))) Description:
(nconc cycle cycle)))
(list-length (circular-list 'a 'b)) NIL ! Returns true if object is of type list; otherwise, returns false .
(list-length (circular-list 'a))
(list-length (circular-list)) 0
NIL
!
! Examples:
Exceptional Situations: (listp nil) ! true
(listp (cons 1 2)) ! true
Should signal an error of type type-error if list is not a proper list or a circular list . (listp (make-array 6)) ! false
! false
See Also: (listp t)
length See Also:

consp
Notes:
list-length could be implemented as follows: Notes:
If object is a cons , listp does not check whether object is a proper list ; it returns true for any kind
(defun list-length (x)
(do ((n 0 (+ n 2)) ;Counter.
of list .
(fast x (cddr fast)) ;Fast pointer: leaps by 2. (listp object ) (typep object 'list) (typep object '(or cons null))

Description:
push prepends item to the list that is stored in place , stores the resulting list in place , and
make-list Function returns the list .
For information about the evaluation of subforms of place , see Section 5.1.1.1 (Evaluation of
Syntax: Subforms to Places).
make-list size &key initial-element ! list Examples:
Arguments and Values: (setq llst '(nil)) ! (NIL)
size |a non-negative integer . (push 1 (car llst)) ! (1)
initial-element |an object . The default is nil. llst ! ((1))

(push 1 (car llst)) ! (1 1)
list |a list . llst ! ((1 1))
(setq x '(a (b c) d)) ! (A (B C) D)
Description: (push 5 (cadr x))
!
!(5 B C)
Returns a list of length given by size , each of the elements of which is initial-element . x (A (5 B C) D)
Examples: Side Eects:

The contents of place are modied.
!
(make-list
(make-list
5) (NIL NIL NIL NIL NIL)
3 :initial-element 'rah) !(RAH RAH RAH) See Also:
(make-list 2 :initial-element '(1 2 3)) !
((1 2 3) (1 2 3)) pop, pushnew, Section 5.1 (Generalized Reference)
! i.e.
(make-list
(make-list
0) NIL ; , ()
0 :initial-element 'new-element) !
NIL Notes:
The eect of (push item place) is equivalent to
Should signal an error of type type-error if size is not a non-negative integer . (setf place (cons item place))
See Also: except that the subforms of place are evaluated only once, and item is evaluated before place .
cons, list
pop Macro
push Macro
Syntax:
pop place ! element
Syntax:
push item place ! new-place-value Arguments and Values:
place |a place , the value of which is a list (possibly, but necessarily, a dotted list or circular list ).
item|an object . element |an object (the car of the contents of place ).
place |a place , the value of which may be any object . Description:
new-place-value |a list (the new value of place ). pop reads the value of place , remembers the car of the list which was retrieved, writes the cdr of
the list back into the place , and nally yields the car of the originally retrieved list .

rst, second, third, fourth, fth, sixth, seventh, :::
For information about the evaluation of subforms of place , see Section 5.1.1.1 (Evaluation of object , new-object |an object .
Subforms to Places).
Description:
Examples: The functions rst, second, third, fourth, fth, sixth, seventh, eighth, ninth, and tenth access
! the rst, second, third, fourth, fth, sixth, seventh, eighth, ninth, and tenth elements of list ,
(setq stack '(a b c)) (A B C) respectively. Specically,
(pop stack) !A
stack ! (B C) (first list ) (car list
)
(setq llst '((1 2 3 4))) !
((1 2 3 4)) (second list ) (car (cdr list
))
(pop (car llst)) !
1 (third list ) (car (cddr list
))
llst ! ((2 3 4)) (fourth list ) (car (cdddr list
))
list ) list
Side Eects: (fifth
(sixth list )
(car
(car
(cddddr ))
(cdr (cddddr ))) list
The contents of place are modied. (seventh list ) (car (cddr (cddddr ))) list
list ) list
See Also: (eighth
(ninth list )
(car
(car
(cdddr (cddddr
(cddddr (cddddr
)))
))) list
push, pushnew, Section 5.1 (Generalized Reference) (tenth list ) (car (cdr (cddddr (cddddr list ))))
Notes: setf can also be used with any of these functions to change an existing component. The same
equivalences apply. For example:
The eect of (pop place ) is roughly equivalent to
(prog1 (car place ) (setf place (cdr place ))) (setf (fifth list ) new-object ) (setf (car (cddddr list )) new-object )
except that the latter would evaluate any subforms of place three times, while pop evaluates them Examples:
only once.
(setq lst '(1 2 3 (4 5 6) ((V)) vi 7 8 9 10))
! (1 2 3 (4 5 6) ((V)) VI 7 8 9 10)
rst, second, third, fourth, fth, sixth, seventh, (first lst) 1 !

!
eighth, ninth, tenth Accessor
(tenth lst)
(fifth lst)
10
!
((V))
(second (fourth lst)) 5 !
(sixth '(1 2 3)) NIL !
Syntax: (setf (fourth lst) "four")
!
"four" !
rst list ! object (setf (rst list) new-object) lst (1 2 3 "four" ((V)) VI 7 8 9 10)
second list ! object (setf (second list) new-object) See Also:
third list ! object (setf (third list) new-object) car, nth
fourth list ! object (setf (fourth list) new-object)
fth list ! object (setf (fth list) new-object) Notes:
sixth list ! object (setf (sixth list) new-object)
rst is functionally equivalent to car, second is functionally equivalent to cadr, third is function-
seventh list ! object (setf (seventh list) new-object)
ally equivalent to caddr, and fourth is functionally equivalent to cadddr.
eighth list ! object (setf (eighth list) new-object)
ninth list ! object (setf (ninth list) new-object) The ordinal numbering used here is one-origin, as opposed to the zero-origin numbering used by
tenth list ! object (setf (tenth list) new-object) nth:
Arguments and Values: (fifth x) (nth 4 x)
list |a list , which might be a dotted list or a circular list .

endp Function
nth Accessor Syntax:
endp list ! generalized-boolean
Syntax: Arguments and Values:
nth n list ! object
list |a list , which might be a dotted list or a circular list .
(setf (nth n list) new-object)
Arguments and Values: Description:
n|a non-negative integer . Returns true if list is the empty list . Returns false if list is a cons .
list |a list , which might be a dotted list or a circular list . Examples:
object |an object . (endp nil) ! true
(endp '(1 2)) ! false
new-object |an object . (endp (cddr '(1 2))) ! true
Description: Exceptional Situations:
nth locates the nth element of list , where the car of the list is the \zeroth" element. Specically, Should signal an error of type type-error if list is not a list .
(nth n list ) (car (nthcdr n list ))
Notes:
nth may be used to specify a place to setf . Specically, The purpose of endp is to test for the end of proper list . Since endp does not descend into a
cons , it is well-dened to pass it a dotted list . However, if shorter \lists" are iteratively produced
(setf (nth n list ) new-object ) (setf (car (nthcdr n list )) new-object ) by calling cdr on such a dotted list and those \lists" are tested with endp, a situation that has
undened consequences will eventually result when the non-nil atom (which is not in fact a list )
nally becomes the argument to endp. Since this is the usual way in which endp is used, it is
Examples: conservative programming style and consistent with the intent of endp to treat endp as simply
! a function on proper lists which happens not to enforce an argument type of proper list except
(nth 0 '(foo bar baz)) FOO when the argument is atomic .
(nth 1 '(foo bar baz)) !BAR
(nth 3 '(foo bar baz)) !NIL
(setq 0-to-3
(setf (nth 2
0-to-3 ! (0
(list 0 1 2 3))
0-to-3) "two")
1 "two" 3)
! (0 1 2 3)
! "two" null Function
See Also: Syntax:

elt, rst, nthcdr null object ! boolean
object |an object .
boolean|a boolean .

Description: Examples:
Returns t if object is the empty list ; otherwise, returns nil.
(nconc) ! NIL
Examples: (setq x '(a b c))
(setq y '(d e f))
!
!
(A B C)
(D E F)
(null !T
'()) (nconc x y) ! (A B C D E F)
(null !T
nil) x ! (A B C D E F)
(null t)! NIL Note, in the example, that the value of x is now dierent, since its last cons has been rplacd'd
(null 1)! NIL to the value of y. If (nconc x y) were evaluated again, it would yield a piece of a circular list ,
whose printed representation would be (A B C D E F D E F D E F ...), repeating forever; if the
See Also: *print-circle* switch were non-nil , it would be printed as (A B C . #1=(D E F . #1#)).
not (setq foo (list 'a 'b 'c 'd 'e)
Notes: bar
baz
(list 'f 'g 'h 'i 'j)
(list 'k 'l 'm)) ! (K L M)
null is intended to be used to test for the empty list whereas not is intended to be used to invert (setq foo (nconc foo bar baz)) ! (A B C D E F G H I J K L M)
a boolean (or generalized boolean ). Operationally, null and not compute the same result; which to foo ! (A B C D E F G H I J K L M)
use is a matter of style. bar ! (F G H I J K L M)
(null object ) (typep object 'null) (eq object '())

baz ! (K L M)
(setq foo (list 'a 'b 'c 'd 'e)
nconc
bar (list 'f 'g 'h 'i 'j)
Function baz (list 'k 'l 'm)) ! (K L M)

(setq foo (nconc nil foo bar nil baz)) ! (A B C D E F G H I J K L M)
foo ! (A B C D E F G H I J K L M)
Syntax: bar ! (F G H I J K L M)
baz ! (K L M)
nconc &rest lists ! concatenated-list
Arguments and Values: Side Eects:
list |each but the last must be a list (which might be a dotted list but must not be a circular The lists are modied rather than copied.
list ); the last list may be any object .
concatenated-list |a list .
See Also:
append, concatenate
Description:
Returns a list that is the concatenation of lists . If no lists are supplied, (nconc) returns nil. nconc
is dened using the following recursive relationship: append Function
(nconc) ! ()
(nconc nil . lists ) (nconc . lists )
list ! list
Syntax:
(nconc
(nconc
)
list-1 list-2 ) (progn (rplacd (last list-1 ) list-2 ) list-1 ) append &rest lists ! result
(nconc list-1 list-2 . lists ) (nconc (nconc list-1 list-2 ) . lists ) Arguments and Values:
list |each must be a proper list except the last, which may be any object .

revappend, nreconc
result |an object . This will be a list unless the last list was not a list and all preceding lists were Examples:
null .
(let ((list-1 (list 1 2 3))
Description: (list-2 (list 'a 'b 'c)))
append returns a new list that is the concatenation of the copies. lists are left unchanged; the list (print (revappend list-1 list-2))
structure of each of lists except the last is copied. The last argument is not copied; it becomes the (print (equal list-1 '(1 2 3)))
cdr of the nal dotted pair of the concatenation of the preceding lists , or is returned directly if (print (equal list-2 '(a b c))))
there are no preceding non-empty lists . . (3 2 1 A B C)
. T
Examples: . T
! T
(append '(a b c) '(d e f) '() '(g)) ! (A B C D E F G)
(append '(a b c) 'd) !
(A B C . D) (revappend '(1 2 3) '()) ! (3 2 1)
(setq lst '(a b c)) !
(A B C) (revappend '(1 !
2 3) '(a . b)) (3 2 1 A . B)
(append lst '(d)) !
(A B C D) (revappend '() '(a b c)) ! (A B C)
lst ! (A B C) (revappend '(1 2 3) 'a) !(3 2 1 . A)
(append) !NIL (revappend '() 'a) ! A ;degenerate case
(append 'a) !
A
See Also: (let ((list-1 '(1 2 3))

(list-2 '(a b c)))
nconc, concatenate (print (nreconc list-1 list-2))
(print (equal list-1 '(1 2 3)))
revappend, nreconc
(print (equal list-2 '(a b c))))
Function . (3 2 1 A B C)
. NIL
. T
Syntax: ! T
revappend list tail ! result-list

nreconc list tail ! result-list Side Eects:
revappend does not modify either of its arguments . nreconc is permitted to modify list but not
Arguments and Values: tail .
list |a proper list . Although it might be implemented dierently, nreconc is constrained to have side-eect behavior
tail |an object . equivalent to:
result-list |an object . (nconc (nreverse list ) tail )
Description: See Also:
revappend constructs a copy 2 of list , but with the elements in reverse order. It then appends (as
if by nconc) the tail to that reversed list and returns the result. reverse , nreverse , nconc
nreconc reverses the order of elements in list (as if by nreverse). It then appends (as if by Notes:
nconc) the tail to that reversed list and returns the result. The following functional equivalences are true, although good implementations will typically use a
The resulting list shares list structure with tail . faster algorithm for achieving the same eect:

(revappend list tail ) (nconc (reverse list ) tail ) (nbutlast (list 'a)) ! NIL
(nreconc list tail ) (nconc (nreverse list ) tail ) (nbutlast '()) !NIL
Should signal an error of type type-error if list is not a proper list or a dotted list . Should signal
butlast, nbutlast Function an error of type type-error if n is not a non-negative integer .
Notes:
Syntax: (butlast list n) (ldiff list (last list n))
butlast list &optional n ! result-list
nbutlast list &optional n ! result-list
list |a list , which might be a dotted list but must not be a circular list .
last Function
n|a non-negative integer . Syntax:
result-list |a list . last list &optional n ! tail
Description: Arguments and Values:
butlast returns a copy of list from which the last n conses have been omitted. If n is not supplied, list |a list , which might be a dotted list but must not be a circular list .
its value is 1. If there are fewer than n conses in list , nil is returned and, in the case of nbutlast, n|a non-negative integer . The default is 1.
list is not modied.
tail |an object .
nbutlast is like butlast, but nbutlast may modify list . It changes the cdr of the cons n+1 from
the end of the list to nil. Description:
Examples: last returns the last n conses (not the last n elements) of list ). If list is (), last returns ().
! If n is zero, the atom that terminates list is returned. If n is greater than or equal to the number
(setq lst '(1 2 3 4 5 6 7 8 9))
(butlast lst) ! (1 2 3 4 5 6 7 8)
(1 2 3 4 5 6 7 8 9)
of cons cells in list , the result is list .
(butlast lst 5) ! (1 2 3 4)
(butlast lst (+ 5 5)) !NIL
Examples:
lst ! (1 2 3 4 5 6 7 8 9) (last nil) !NIL
(nbutlast lst 3) ! (1 2 3 4 5 6) (last '(1 2 3)) !(3)
lst ! (1 2 3 4 5 6) (last '(1 2 . 3)) ! (2 . 3)
(nbutlast lst 99) ! NIL (setq x (list 'a 'b 'c 'd)) !
(A B C D)
lst ! (1 2 3 4 5 6) (last x) !(D)
(butlast '(a b c d)) !(A B C) (rplacd (last x) (list 'e 'f)) x !
(A B C D E F)
(butlast '((a b) (c d))) !
((A B)) (last x) !(F)
(butlast '(a)) ! NIL
(butlast nil) ! NIL (last '(a b c)) ! (C)
(setq foo (list 'a 'b 'c 'd)) !
(A B C D)
(nbutlast foo) ! (A B C) (last '(a b c) 0) ! ()
foo ! (A B C) (last '(a b c) 1) ! (C)

ldi, tailp
(last '(a b c) 2) ! (B C) Description:
(last '(a b c) 3) ! (A B C) If object is the same as some tail of list , tailp returns true ; otherwise, it returns false .
(last '(a b c) 4) ! (A B C)
If object is the same as some tail of list , ldi returns a fresh list of the elements of list that
(last '(a . b) 0) ! B precede object in the list structure of list ; otherwise, it returns a copy 2 of list .
(last '(a . b) 1) ! (A . B)
(last '(a . b) 2) ! (A . B) Examples:
(let ((lists '#((a b c) (a b c . d))))
Exceptional Situations: (dotimes (i (length lists)) ()
The consequences are undened if list is a circular list . Should signal an error of type type-error (let ((list (aref lists i)))
if n is not a non-negative integer . (format t "~2&list=~S ~21T(tailp object list)~

~44T(ldiff list object)~%" list)
See Also: (let ((objects (vector list (cddr list) (copy-list (cddr list))
butlast, nth '(f g h) '() 'd 'x)))

(dotimes (j (length objects)) ()
Notes: (let ((object (aref objects j)))
The following code could be used to dene last. (format t "~& object=~S ~21T~S ~44T~S"
object (tailp object list) (ldiff list object))))))))
(defun last (list &optional (n 1)) .
(check-type n (integer 0)) . list=(A B C) (tailp object list) (ldiff list object)
(do ((l list (cdr l)) . object=(A B C) T NIL
(r list) . object=(C) T (A B)
(i 0 (+ i 1))) . object=(C) NIL (A B C)
((atom l) r) . object=(F G H) NIL (A B C)
(if (>= i n) (pop r)))) . object=NIL T (A B C)
. object=D NIL (A B C)
. object=X NIL (A B C)
.
ldi, tailp Function . list=(A B C . D)

. object=(A B C . D) T
. object=(C . D)
(tailp object list)
T
(ldiff list object)
NIL
(A B)
Syntax: . object=(C . D)
. object=(F G H)
NIL
NIL
(A B C . D)
(A B C . D)
ldi list object ! result-list . object=NIL NIL (A B C . D)
. object=D T (A B C)
tailp object list ! generalized-boolean . object=X NIL (A B C . D)
Arguments and Values: ! NIL
list |a list , which might be a dotted list .

object |an object . Side Eects:
Neither ldi nor tailp modies either of its arguments .
result-list |a list .
generalized-boolean|a generalized boolean . Should be prepared to signal an error of type type-error if list is not a proper list or a dotted list .

Examples:
See Also: (nthcdr 0 '()) ! NIL
set-dierence (nthcdr 3 '()) ! NIL
(nthcdr 0 '(a b c)) ! (A B C)
Notes: (nthcdr 2 '(a b c)) ! (C)
If the list is a circular list , tailp will reliably yield a value only if the given object is in fact a (nthcdr 4 '(a b c)) ! ()
tail of list . Otherwise, the consequences are unspecied: a given implementation which detects (nthcdr 1 '(0 . 1)) ! 1
the circularity must return false , but since an implementation is not obliged to detect such a
situation , tailp might just loop indenitely without returning in that case. (locally (declare (optimize (safety 3)))
(nthcdr 3 '(0 . 1)))
tailp could be dened as follows: Error: Attempted to take CDR of 1.
(defun tailp (object list) Exceptional Situations:

(do ((list list (cdr list)))
((atom list) (eql list object))
Should signal an error of type type-error if n is not a non-negative integer .
(if (eql object list) For n being an integer greater than 1, the error checking done by (nthcdr n list ) is the same as
(return t)))) for (nthcdr (- n 1) (cdr list )); see the function cdr.
and ldi could be dened by: See Also:
(defun ldiff (list object) cdr, nth, rest
(do ((list list (cdr list))
(r '() (cons (car list) r)))
((atom list)
(if (eql list object) (nreverse r) (nreconc r list)))
rest Accessor
(when (eql object list)
(return (nreverse r))))) Syntax:
rest list ! tail
(setf (rest list) new-tail)
nthcdr Function
Syntax: list |a list , which might be a dotted list or a circular list .
nthcdr n list ! tail tail |an object .
Arguments and Values: Description:
n|a non-negative integer . rest performs the same operation as cdr, but mnemonically complements rst. Specically,
list |a list , which might be a dotted list or a circular list . (rest list ) (cdr list )
(setf (rest list ) new-tail ) (setf (cdr list ) new-tail )
tail |an object .
Description: Examples:
Returns the tail of list that would be obtained by calling cdr n times in succession. (rest '(1 2)) ! (2)

(rest '(1 . 2)) ! 2 Examples:

(rest '(1)) ! NIL
(setq *cons* '(1 . 2)) !
(1 . 2) (member 2 '(1 2 3)) !(2 3)
(setf (rest *cons*) "two") !
"two" (member 2 '((1 . 2) (3 . 4)) :test-not #'= :key #'cdr) ! ((3 . 4))
*cons* ! (1 . "two") (member 'e '(a b c d)) !
NIL
See Also: (member-if #'listp '(a b nil c d)) !

(NIL C D)
!
cdr, nthcdr (member-if #'numberp '(a #\Space 5/3 foo))
(member-if-not #'zerop
(5/3 FOO)
Notes: '(3 6 9 11 . 12)

!
rest is often preferred stylistically over cdr when the argument is to being subjectively viewed as :key #'(lambda (x) (mod x 3))) (11 . 12)
a list rather than as a cons . Exceptional Situations:

Should be prepared to signal an error of type type-error if list is not a proper list .
member, member-if, member-if-not Function See Also:
nd, position, Section 3.6 (Traversal Rules and Side Eects)
Syntax: Notes:
member item list &key key test test-not ! tail The :test-not parameter is deprecated.
member-if predicate list &key key ! tail The function member-if-not is deprecated.
member-if-not predicate list &key key ! tail In the following
Arguments and Values: (member 'a '(g (a y) c a d e a f)) ! (A D E A F)
item|an object . the value returned by member is identical to the portion of the list beginning with a. Thus
list |a proper list . rplaca on the result of member can be used to alter the part of the list where a was found
(assuming a check has been made that member did not return nil).
predicate |a designator for a function of one argument that returns a generalized boolean .
test-not |a designator for a function of two arguments that returns a generalized boolean .
mapc,
Function
mapcar, mapcan, mapl, maplist, mapcon
tail |a list . Syntax:
mapc function &rest lists+ ! list-1
Description: mapcar function &rest lists+ ! result-list
member, member-if , and member-if-not each search list for item or for a top-level element that
satises the test . The argument to the predicate function is an element of list . mapcan function &rest lists+ ! concatenated-results
If some element satises the test , the tail of list beginning with this element is returned; otherwise
nil is returned. mapl function &rest lists+ ! list-1
list is searched on the top level only. maplist function &rest lists+ ! result-list

mapc, mapcar, mapcan, mapl, maplist, mapcon

mapcon function &rest lists+ ! concatenated-results (mapcar #'cons '(a b c) '(1 2 3)) ! ((A . 1) (B . 2) (C . 3))
Arguments and Values: (maplist #'append '(1 2 3 4) '(1 2) '(1 2 3))

function|a designator for a function that must take as many arguments as there are lists . ! ((1 2 3 4 1 2 1 2 3) (2 3 4 2 2 3))
(maplist #'(lambda (x) (cons 'foo x)) '(a b c d))
list |a proper list . ! ((FOO A B C D) (FOO B C D) (FOO C D) (FOO D))
list-1 |the rst list (which must be a proper list ). (maplist #'(lambda (x) (if (member (car x) (cdr x)) 0 1)) '(a b a c
! (0 0 1 0 1 1 1)
d b c))
result-list |a list . ;An entry is 1 if the corresponding element of the input

; list was the last instance of that element in the input list.
concatenated-results |a list .
!
Description: (setq dummy nil) NIL
(mapc #'(lambda (&rest x) (setq dummy (append dummy x)))
The mapping operation involves applying function to successive sets of arguments in which one '(1 2 3 4)
argument is obtained from each sequence . Except for mapc and mapl, the result contains the '(a b c d e)
results returned by function. In the cases of mapc and mapl, the resulting sequence is list . '(x y z)) !(1 2 3 4)
dummy ! (1 A X 2 B Y 3 C Z)
function is called rst on all the elements with index 0, then on all those with index 1, and so on.
result-type species the type of the resulting sequence . If function is a symbol , it is coerced to a (setq dummy nil) !NIL
function as if by symbol-function. (mapl #'(lambda (x) (push x dummy)) '(1 2 3 4)) ! (1 2 3 4)
mapcar operates on successive elements of the lists . function is applied to the rst element of dummy ! ((4) (3 4) (2 3 4) (1 2 3 4))
each list , then to the second element of each list , and so on. The iteration terminates when
the shortest list runs out, and excess elements in other lists are ignored. The value returned by (mapcan #'(lambda (x y) (if (null x) nil (list x y)))
mapcar is a list of the results of successive calls to function. '(nil nil nil d e)
'(1 2 3 4 5 6)) !(D 4 E 5)
mapc is like mapcar except that the results of applying function are not accumulated. The list (mapcan #'(lambda (x) (and (numberp x) (list x)))
argument is returned. '(a 1 b c 3 4 d 5))
! (1 3 4 5)
maplist is like mapcar except that function is applied to successive sublists of the lists . function
is rst applied to the lists themselves, and then to the cdr of each list , and then to the cdr of the In this case the function serves as a lter; this is a standard Lisp idiom using mapcan.
cdr of each list , and so on. (mapcon #'list '(1 2 3 4)) ! ((1 2 3 4) (2 3 4) (3 4) (4))
mapl is like maplist except that the results of applying function are not accumulated; list-1 is Exceptional Situations:
returned.
Should be prepared to signal an error of type type-error if any list is not a proper list .
mapcan and mapcon are like mapcar and maplist respectively, except that the results of apply-
ing function are combined into a list by the use of nconc rather than list. That is, See Also:
(mapcon f x1 ... xn)
dolist, map, Section 3.6 (Traversal Rules and Side Eects)
(apply #'nconc (maplist f x1 ... xn))
and similarly for the relationship between mapcan and mapcar.

Examples:
(mapcar #'car '((1 a) (2 b) (3 c))) !
(1 2 3)
(mapcar #'abs '(3 -4 2 -5 -6)) !
(3 4 2 5 6)

assoc, assoc-if, assoc-if-not

acons Function assoc-if-not predicate alist &key key ! entry

acons key datum alist ! new-alist item|an object .
Arguments and Values: alist |an association list .
key |an object . predicate |a designator for a function of one argument that returns a generalized boolean .
datum|an object . test |a designator for a function of two arguments that returns a generalized boolean .
alist |an association list . test-not |a designator for a function of two arguments that returns a generalized boolean .
new-alist |an association list . key |a designator for a function of one argument, or nil.
Description: entry |a cons that is an element of alist , or nil.
Creates a fresh cons , the cdr of which is alist and the car of which is another fresh cons , the car
of which is key and the cdr of which is datum. Description:
assoc , assoc-if , and assoc-if-not return the rst cons in alist whose car satises the test , or nil if
Examples: no such cons is found.
(setq alist '()) !NIL For assoc, assoc-if , and assoc-if-not, if nil appears in alist in place of a pair, it is ignored.
!
Examples:
(acons 1 "one" alist) ((1 . "one"))
alist !NIL
(setq alist (acons 1 "one" (acons 2 "two" alist))) !
((1 . "one") (2 . "two"))
(assoc 1 alist) !(1 . "one") (setq values '((x . 100) (y . 200) (z . 50))) !
((X . 100) (Y . 200) (Z . 50))
(setq alist (acons 1 "uno" alist)) !
((1 . "uno") (1 . "one") (2 . "two")) (assoc 'y values) !(Y . 200)
(assoc 1 alist) !(1 . "uno") (rplacd (assoc 'y values) 201) !
(Y . 201)
(assoc 'y values) !(Y . 201)
See Also: (setq alist '((1 . "one")(2 . "two")(3 . "three")))
assoc , pairlis ! ((1 . "one") (2 . "two") (3 . "three"))
(assoc 2 alist) ! (2 . "two")
Notes: (assoc-if #'evenp alist) !
(2 . "two")
(assoc-if-not #'(lambda(x) (< x 3)) alist) !
(3 . "three")
(acons key datum alist ) (cons (cons key datum) alist ) (setq alist '(("one" . 1)("two" . 2))) !
(("one" . 1) ("two" . 2))
(assoc "one" alist) !NIL
(assoc "one" alist :test #'equalp) !
("one" . 1)
!
assoc, assoc-if, assoc-if-not
(assoc "two" alist :key #'(lambda(x) (char x 2))) NIL
Function (assoc #\o alist :key #'(lambda(x) (char x 2))) !

("two" . 2)
(assoc 'r '((a . b) (c . d) (r . x) (s . y) (r . z))) !
(R . X)
(assoc 'goo '((foo . bar) (zoo . goo))) !
NIL
Syntax: (assoc '2 '((1 a b c) (2 b c d) (-7 x y z))) !

(2 B C D)
(setq alist '(("one" . 1) ("2" . 2) ("three" . 3)))
assoc item alist &key key test test-not ! entry ! (("one" . 1) ("2" . 2) ("three" . 3))
assoc-if predicate alist &key key ! entry (assoc-if-not #'alpha-char-p alist
:key #'(lambda (x) (char x 0))) !
("2" . 2)

Exceptional Situations: Examples:

Should be prepared to signal an error of type type-error if alist is not an association list .
(defparameter *alist* (acons 1 "one" (acons 2 "two" '())))
See Also: *alist* ! ((1 . "one") (2 . "two"))
rassoc , nd, member, position, Section 3.6 (Traversal Rules and Side Eects) (defparameter *list-copy* (copy-list *alist*))
*list-copy* !((1 . "one") (2 . "two"))
Notes: (defparameter *alist-copy* (copy-alist *alist*))
!
The :test-not parameter is deprecated. *alist-copy* ((1 . "one") (2 . "two"))
(setf (cdr (assoc 2 *alist-copy*)) "deux") !
"deux"
The function assoc-if-not is deprecated. *alist-copy* ! ((1 . "one") (2 . "deux"))
*alist* ! ((1 . "one") (2 . "two"))
It is possible to rplacd the result of assoc, provided that it is not nil, in order to \update" alist . (setf (cdr (assoc 1 *list-copy*)) "uno") !
"uno"
The two expressions *list-copy* !((1 . "uno") (2 . "two"))

*alist* ! ((1 . "uno") (2 . "two"))
(assoc item list :test fn)
See Also:
and copy-list
(find item list :test fn :key #'car)
are equivalent in meaning with one exception: if nil appears in alist in place of a pair, and item
is nil, nd will compute the car of the nil in alist , nd that it is equal to item, and return nil,
pairlis Function
whereas assoc will ignore the nil in alist and continue to search for an actual cons whose car is
nil. Syntax:
pairlis keys data &optional alist ! new-alist
copy-alist Function Arguments and Values:
keys |a proper list .
Syntax: data|a proper list .
copy-alist alist ! new-alist alist |an association list . The default is the empty list .
Arguments and Values: new-alist |an association list .
alist |an association list .
Description:
new-alist |an association list . Returns an association list that associates elements of keys to corresponding elements of data.
The consequences are undened if keys and data are not of the same length .
Description:
copy-alist returns a copy of alist . If alist is supplied, pairlis returns a modied alist with the new pairs prepended to it. The new
pairs may appear in the resulting association list in either forward or backward order. The result
The list structure of alist is copied, and the elements of alist which are conses are also copied (as of
conses only). Any other objects which are referred to, whether directly or indirectly, by the alist
continue to be shared. (pairlis '(one two) '(1 2) '((three . 3) (four . 19)))
might be
((one . 1) (two . 2) (three . 3) (four . 19))

or Description:
rassoc , rassoc-if , and rassoc-if-not return the rst cons whose cdr satises the test . If no such
((two . 2) (one . 1) (three . 3) (four . 19))
cons is found, nil is returned.
Examples: If nil appears in alist in place of a pair, it is ignored.
(setq keys '(1 2 3)
data '("one" "two" "three")
Examples:
alist '((4 . "four"))) !
((4 . "four")) (setq alist '((1 . "one") (2 . "two") (3 . 3)))
(pairlis keys data) !((3 . "three") (2 . "two") (1 . "one")) ! ((1 . "one") (2 . "two") (3 . 3))
(pairlis keys data alist) (rassoc 3 alist) ! (3 . 3)
! ((3 . "three") (2 . "two") (1 . "one") (4 . "four")) (rassoc "two" alist) ! NIL
alist ! ((4 . "four")) (rassoc "two" alist :test 'equal) ! (2 . "two")
(rassoc 1 alist :key #'(lambda (x) (if (numberp x) (/ x 3)))) ! (3 . 3)
Exceptional Situations: (rassoc 'a '((a . b) (b . c) (c . a) (z . a))) ! (C . A)
Should be prepared to signal an error of type type-error if keys and data are not proper lists . (rassoc-if #'stringp alist) ! (1 . "one")
(rassoc-if-not #'vectorp alist) ! (3 . 3)
See Also:
acons See Also:
assoc , Section 3.6 (Traversal Rules and Side Eects)
rassoc, rassoc-if, rassoc-if-not Function Notes:
The :test-not parameter is deprecated.
Syntax: The function rassoc-if-not is deprecated.
rassoc item alist &key key test test-not ! entry It is possible to rplaca the result of rassoc, provided that it is not nil, in order to \update" alist .
rassoc-if predicate alist &key key ! entry The expressions
rassoc-if-not predicate alist &key key ! entry (rassoc item list :test fn)
and
Arguments and Values: (find item list :test fn :key #'cdr)
item|an object .
are equivalent in meaning, except when the item is nil and nil appears in place of a pair in the
alist |an association list . alist . See the function assoc.
predicate |a designator for a function of one argument that returns a generalized boolean .
test |a designator for a function of two arguments that returns a generalized boolean . get-properties Function
test-not |a designator for a function of two arguments that returns a generalized boolean .
key |a designator for a function of one argument, or nil. Syntax:
get-properties plist indicator-list ! indicator, value, tail
entry |a cons that is an element of the alist , or nil.

getf
plist |a property list . indicator |an object .
indicator-list |a proper list (of indicators ). default |an object . The default is nil.
indicator |an object that is an element of indicator-list . value |an object .
value |an object . new-value |an object .
tail |a list . Description:
Description: getf nds a property on the plist whose property indicator is identical to indicator , and returns
its corresponding property value . If there are multiple properties 1 with that property indicator ,
get-properties is used to look up any of several property list entries all at once. getf uses the rst such property . If there is no property with that property indicator , default is
It searches the plist for the rst entry whose indicator is identical to one of the objects in returned.
indicator-list . If such an entry is found, the indicator and value returned are the property indi- setf of getf may be used to associate a new object with an existing indicator in the property list
cator and its associated property value , and the tail returned is the tail of the plist that begins held by place , or to create a new assocation if none exists. If there are multiple properties 1 with
with the found entry (i.e., whose car is the indicator ). If no such entry is found, the indicator , that property indicator , setf of getf associates the new-value with the rst such property . When
value , and tail are all nil. a getf form is used as a setf place , any default which is supplied is evaluated according to normal
Examples: left-to-right evaluation rules, but its value is ignored.
setf of getf is permitted to either write the value of place itself, or modify of any part, car or
(setq x '()) !NIL cdr , of the list structure held by place .
(setq *indicator-list* '(prop1 prop2)) !
(PROP1 PROP2)
(getf x 'prop1) !
NIL
(setf (getf x 'prop1) 'val1) !
VAL1
Examples:
(eq (getf x 'prop1) 'val1) ! true (setq x '()) !NIL
(get-properties x *indicator-list*) !
PROP1, VAL1, (PROP1 VAL1) (getf x 'prop1) !
NIL
x ! (PROP1 VAL1) (getf x 'prop1 7) !7
!
See Also:
(getf x 'prop1) NIL
(setf (getf x 'prop1) 'val1) ! VAL1
get, getf (eq (getf x 'prop1) 'val1) ! true
(getf x 'prop1) !
VAL1
!
getf
(getf x 'prop1 7) VAL1
Accessor x ! (PROP1 VAL1)
;; Examples of implementation variation permitted.
Syntax: (setq foo (list 'a 'b 'c 'd 'e 'f)) !
(A B C D E F)
(setq bar (cddr foo)) !
(C D E F)
getf plist indicator &optional default ! value (remf foo 'c) ! true
(setf (getf place indicator &optional default) new-value) foo ! (A B E F)
bar
! (C D E F)
Arguments and Values: !
or
!
or
(C)
plist |a property list . !
or
(NIL)
(C NIL)
place |a place , the value of which is a property list . !
or
(C D)

See Also: Examples:

get, get-properties, setf , Section 5.1.2.2 (Function Call Forms as Places) (setq x (cons () ())) ! (NIL)
Notes: (setf (getf (car x) 'prop1) 'val1)
! true
! VAL1
There is no way (using getf ) to distinguish an absent property from one whose value is default ; (remf (car x) 'prop1)
! false
but see get-properties. (remf (car x) 'prop1)
Note that while supplying a default argument to getf in a setf situation is sometimes not very Side Eects:
interesting, it is still important because some macros, such as push and incf , require a place The property list stored in place is modied.
argument which data is both read from and written to. In such a context, if a default argument is
to be supplied for the read situation, it must be syntactically valid for the write situation as well. See Also:
For example, remprop, getf
(let ((plist '()))
(incf (getf plist 'count 0))
plist) ! (COUNT 1) intersection, nintersection Function
Syntax:
remf Macro intersection list-1 list-2 &key key test test-not ! result-list
nintersection list-1 list-2 &key key test test-not ! result-list
remf place indicator ! generalized-boolean list-1 |a proper list .
Arguments and Values: list-2 |a proper list .
place |a place . test |a designator for a function of two arguments that returns a generalized boolean .
indicator |an object . test-not |a designator for a function of two arguments that returns a generalized boolean .
generalized-boolean|a generalized boolean . key |a designator for a function of one argument, or nil.
Description: result-list |a list .
remf removes from the property list stored in place a property 1 with a property indicator identical
to indicator . If there are multiple properties 1 with the identical key, remf only removes the rst Description:
such property . remf returns false if no such property was found, or true if a property was found. intersection and nintersection return a list that contains every element that occurs in both list-1
The property indicator and the corresponding property value are removed in an undened order and list-2 .
by destructively splicing the property list. remf is permitted to either setf place or to setf any nintersection is the destructive version of intersection. It performs the same operation, but may
part, car or cdr, of the list structure held by that place . destroy list-1 using its cells to construct the result. list-2 is not destroyed.
For information about the evaluation of subforms of place , see Section 5.1.1.1 (Evaluation of The intersection operation is described as follows. For all possible ordered pairs consisting of one
Subforms to Places). element from list-1 and one element from list-2 , :test or :test-not are used to determine whether
they satisfy the test . The rst argument to the :test or :test-not function is an element of list-1 ;
the second argument is an element of list-2 . If :test or :test-not is not supplied, eql is used. It is
an error if :test and :test-not are supplied in the same function call.

intersection, nintersection
If :key is supplied (and not nil), it is used to extract the part to be tested from the list element. tions in portable code.
The argument to the :key function is an element of either list-1 or list-2 ; the :key function
typically returns part of the supplied element. If :key is not supplied or nil, the list-1 and list-2
elements are used. adjoin Function
For every pair that saties the test , exactly one of the two elements of the pair will be put in
the result. No element from either list appears in the result that does not satisfy the test for
an element from the other list . If one of the lists contains duplicate elements, there may be Syntax:
duplication in the result. adjoin item list &key key test test-not ! new-list
There is no guarantee that the order of elements in the result will re ect the ordering of the Arguments and Values:
arguments in any particular way. The result list may share cells with, or be eq to, either list-1 or item|an object .
list-2 if appropriate.
list |a proper list .
Examples: test |a designator for a function of two arguments that returns a generalized boolean .
(setq list1 (list 1 1 2 3 4 a b c "A" "B" "C" "d")
list2 (list 1 4 5 b c d "a" "B" "c" "D")) test-not |a designator for a function of two arguments that returns a generalized boolean .
! (1 4 5 B C D "a" "B" "c" "D")
(intersection list1 list2) !
(C B 4 1 1)
(intersection list1 list2 :test 'equal) !
("B" C B 4 1 1) new-list |a list .
!
Description:
(intersection list1 list2 :test #'equalp) ("d" "C" "B" "A" C B 4 1 1)
(nintersection list1 list2) ! (1 1 4 B C)
list1 ! implementation-dependent e.g.
; , (1 1 4 B C) Tests whether item is the same as an existing element of list . If the item is not an existing ele-
; , (1 4 5 B C D "a" "B" "c" "D") ment, adjoin adds it to list (as if by cons) and returns the resulting list ; otherwise, nothing is
(setq list1 (copy-list '((1 . 2) (2 . 3) (3 . 4) (4 . 5)))) added and the original list is returned.
! ((1 . 2) (2 . 3) (3 . 4) (4 . 5))
(setq list2 (copy-list '((1 . 3) (2 . 4) (3 . 6) (4 . 8)))) The test , test-not , and key aect how it is determined whether item is the same as an element of
! ((1 . 3) (2 . 4) (3 . 6) (4 . 8)) list . For details, see Section 17.2.1 (Satisfying a Two-Argument Test).
!
(nintersection list1 list2 :key #'cdr)
;
((2 . 3) (3 . 4))
, ((1 . 2) (2 . 3) (3 . 4)) Examples:
; , ((1 . 3) (2 . 4) (3 . 6) (4 . 8))
(setq slist '()) !NIL
Side Eects: (adjoin 'a slist)
!
! (A)
nintersection can modify list-1 , but not list-2 . slist NIL

(setq slist (adjoin '(test-item 1) slist)) !
((TEST-ITEM 1))
Exceptional Situations: (adjoin '(test-item 1) slist) !
((TEST-ITEM 1) (TEST-ITEM 1))
!
Should be prepared to signal an error of type type-error if list-1 and list-2 are not proper lists . (adjoin '(test-item 1) slist :test 'equal)
(adjoin '(new-test-item 1) slist :key #'cadr)
((TEST-ITEM 1))
!
((TEST-ITEM 1))
See Also: (adjoin '(new-test-item 1) slist) !
((NEW-TEST-ITEM 1) (TEST-ITEM 1))
union, Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Side Eects) Exceptional Situations:
Notes: Should be prepared to signal an error of type type-error if list is not a proper list .
The :test-not parameter is deprecated. See Also:
Since the nintersection side eect is not required, it should not be used in for-eect-only posi- pushnew, Section 3.6 (Traversal Rules and Side Eects)

Notes: It is implementation-dependent whether or not pushnew actually executes the storing form for its
The :test-not parameter is deprecated. place in the situation where the item is already a member of the list held by place .
(adjoin item list :key fn) Examples:
(if (member (fn item) list :key fn) list (cons item list))
(setq x '(a (b c) d)) ! (A (B C) D)
(pushnew 5 (cadr x)) !(5 B C)
!
pushnew
x (A (5 B C) D)
Macro (pushnew 'b (cadr x)) ! (5 B C)

x ! (A (5 B C) D)
(setq lst '((1) (1 2) (1 2 3))) !
((1) (1 2) (1 2 3))
!
Syntax: (pushnew '(2) lst)
(pushnew '(1) lst) !
((2) (1) (1 2) (1 2 3))
((1) (2) (1) (1 2) (1 2 3))
pushnew item place &key key test test-not (pushnew '(1) lst :test 'equal) !
((1) (2) (1) (1 2) (1 2 3))
! new-place-value (pushnew '(1) lst :key #'car) !
((1) (2) (1) (1 2) (1 2 3))
Arguments and Values: Side Eects:

item|an object . The contents of place may be modied.
place |a place , the value of which is a proper list . See Also:
test |a designator for a function of two arguments that returns a generalized boolean . push, adjoin, Section 5.1 (Generalized Reference)
test-not |a designator for a function of two arguments that returns a generalized boolean . Notes:
The eect of (pushnew item place :test p)
is roughly equivalent to (setf place (adjoin item place :test p))
new-place-value |a list (the new value of place ).
except that the subforms of place are evaluated only once, and item is evaluated before place.
Description:
pushnew tests whether item is the same as any existing element of the list stored in place . If item
is not, it is prepended to the list , and the new list is stored in place . set-dierence, nset-dierence Function
pushnew returns the new list that is stored in place .
Whether or not item is already a member of the list that is in place is determined by comparisons Syntax:
using :test or :test-not. The rst argument to the :test or :test-not function is item; the set-dierence list-1 list-2 &key key test test-not ! result-list
second argument is an element of the list in place as returned by the :key function (if supplied).
nset-dierence list-1 list-2 &key key test test-not ! result-list
If :key is supplied, it is used to extract the part to be tested from both item and the list element,
as for adjoin. Arguments and Values:
The argument to the :key function is an element of the list stored in place . The :key function list-1 |a proper list .
typically returns part part of the element of the list . If :key is not supplied or nil, the list ele- list-2 |a proper list .
ment is used.
For information about the evaluation of subforms of place , see Section 5.1.1.1 (Evaluation of
Subforms to Places). test-not |a designator for a function of two arguments that returns a generalized boolean .

set-dierence, nset-dierence

key |a designator for a function of one argument, or nil. Side Eects:
result-list |a list . nset-dierence may destroy list-1 .
set-dierence returns a list of elements of list-1 that do not appear in list-2 . Should be prepared to signal an error of type type-error if list-1 and list-2 are not proper lists .
nset-dierence is the destructive version of set-dierence. It may destroy list-1 . See Also:
Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Side Eects)
For all possible ordered pairs consisting of one element from list-1 and one element from list-2 , the
:test or :test-not function is used to determine whether they satisfy the test . The rst argument Notes:
to the :test or :test-not function is the part of an element of list-1 that is returned by the :key The :test-not parameter is deprecated.
function (if supplied); the second argument is the part of an element of list-2 that is returned by
the :key function (if supplied).
If :key is supplied, its argument is a list-1 or list-2 element. The :key function typically returns
part of the supplied element. If :key is not supplied, the list-1 or list-2 element is used.
set-exclusive-or, nset-exclusive-or Function
An element of list-1 appears in the result if and only if it does not match any element of list-2 . Syntax:
There is no guarantee that the order of elements in the result will re ect the ordering of the set-exclusive-or list-1 list-2 &key key test test-not ! result-list
arguments in any particular way. The result list may share cells with, or be eq to, either of list-1 nset-exclusive-or list-1 list-2 &key key test test-not ! result-list
or list-2 , if appropriate.
Examples: Arguments and Values:
list-1 |a proper list .
(setq lst1 (list "A" "b" "C" "d") list-2 |a proper list .
lst2 (list "a" "B" "C" "d")) !
("a" "B" "C" "d")
(set-difference lst1 lst2) !
("d" "C" "b" "A") test |a designator for a function of two arguments that returns a generalized boolean .
(set-difference lst1 lst2 :test 'equal) !
("b" "A")
(set-difference lst1 lst2 :test #'equalp) !
NIL test-not |a designator for a function of two arguments that returns a generalized boolean .
(nset-difference lst1 lst2 :test #'string=) !("A" "b")
(setq lst1 '(("a" . "b") ("c" . "d") ("e" . "f")))
! (("a" . "b") ("c" . "d") ("e" . "f")) result-list |a list .
(setq lst2 '(("c" . "a") ("e" . "b") ("d" . "a")))
! (("c" . "a") ("e" . "b") ("d" . "a")) Description:
(nset-difference lst1 lst2 :test #'string= :key #'cdr) set-exclusive-or returns a list of elements that appear in exactly one of list-1 and list-2 .
! (("c" . "d") ("e" . "f"))
lst1 ! (("a" . "b") ("c" . "d") ("e" . "f")) nset-exclusive-or is the destructive version of set-exclusive-or.
lst2 ! (("c" . "a") ("e" . "b") ("d" . "a"))
For all possible ordered pairs consisting of one element from list-1 and one element from list-2 , the
;; Remove all flavor names that contain "c" or "w". :test or :test-not function is used to determine whether they satisfy the test .
(set-difference '("strawberry" "chocolate" "banana"
"lemon" "pistachio" "rhubarb") If :key is supplied, it is used to extract the part to be tested from the list-1 or list-2 element. The
'(#\c #\w) rst argument to the :test or :test-not function is the part of an element of list-1 extracted by
:test #'(lambda (s c) (find c s))) the :key function (if supplied); the second argument is the part of an element of list-2 extracted
! ("banana" "rhubarb" "lemon") ;One possible ordering. by the :key function (if supplied). If :key is not supplied or nil, the list-1 or list-2 element is used.

The result contains precisely those elements of list-1 and list-2 that appear in no matching pair. Arguments and Values:
The result list of set-exclusive-or might share storage with one of list-1 or list-2 . list-1 |a proper list .
Examples:
(setq lst1 (list 1 "a" "b")
lst2 (list 1 "A" "b")) !
(1 "A" "b") test-not |a designator for a function of two arguments that returns a generalized boolean .
(set-exclusive-or lst1 lst2) !
("b" "A" "b" "a")
(set-exclusive-or lst1 lst2 :test #'equal) !
("A" "a")
(set-exclusive-or lst1 lst2 :test 'equalp) !
NIL
(nset-exclusive-or lst1 lst2) !
("a" "b" "A" "b")
!
(setq lst1 (list (("a" . "b") ("c" . "d") ("e" . "f")))) Description:
(("a" . "b") ("c" . "d") ("e" . "f"))
(setq lst2 (list (("c" . "a") ("e" . "b") ("d" . "a"))))
subsetp returns true if every element of list-1 matches some element of list-2 , and false otherwise.
! (("c" . "a") ("e" . "b") ("d" . "a")) Whether a list element is the same as another list element is determined by the functions specied
(nset-exclusive-or lst1 lst2 :test #'string= :key #'cdr) by the keyword arguments. The rst argument to the :test or :test-not function is typically
! (("c" . "d") ("e" . "f") ("c" . "a") ("d" . "a")) part of an element of list-1 extracted by the :key function; the second argument is typically part
lst1 ! (("a" . "b") ("c" . "d") ("e" . "f")) of an element of list-2 extracted by the :key function.
lst2 ! (("c" . "a") ("d" . "a"))
The argument to the :key function is an element of either list-1 or list-2 ; the return value is
Side Eects: part of the element of the supplied list element. If :key is not supplied or nil, the list-1 or list-2
nset-exclusive-or is permitted to modify any part, car or cdr , of the list structure of list-1 or element itself is supplied to the :test or :test-not function.
list-2 .
Examples:
Exceptional Situations: !
Should be prepared to signal an error of type type-error if list-1 and list-2 are not proper lists . (setq cosmos '(1 "a" (1 2)))
(subsetp '(1) cosmos) ! true
(1 "a" (1 2))
See Also: (subsetp '((1 2)) cosmos) ! false

Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Side Eects) (subsetp '((1 2)) cosmos :test 'equal) ! true
(subsetp '(1 "A") cosmos :test #'equalp) ! true
Notes: (subsetp '((1) (2)) '((1) (2))) ! false
The :test-not parameter is deprecated. (subsetp '((1) (2)) '((1) (2)) :key #'car) ! true
Since the nset-exclusive-or side eect is not required, it should not be used in for-eect-only Exceptional Situations:
positions in portable code. Should be prepared to signal an error of type type-error if list-1 and list-2 are not proper lists .
See Also:
subsetp Function
Notes:
Section 3.6 (Traversal Rules and Side Eects)
Syntax: The :test-not parameter is deprecated.

subsetp list-1 list-2 &key key test test-not ! generalized-boolean

union, nunion union, nunion

union, nunion Function Examples:
(union '(a b c) '(f a d))
Syntax: !
!
or
(A B C F D)
union list-1 list-2 &key key test test-not ! result-list (B C F A D)
! (D F A B C)
or
nunion list-1 list-2 &key key test test-not ! result-list (union '((x 5) (y 6)) '((z 2) (x 4)) :key #'car)
!
((X 5) (Y 6) (Z 2))
! ((X 4) (Y 6) (Z 2))
or

(setq lst1 (list 1 2 '(1 2) "a" "b")
list-2 |a proper list . lst2 (list 2 3 '(2 3) "B" "C"))
test |a designator for a function of two arguments that returns a generalized boolean . ! (2 3 (2 3) "B" "C")
(nunion lst1 lst2)
test-not |a designator for a function of two arguments that returns a generalized boolean . ! (1 (1 2) "a" "b" 2 3 (2 3) "B" "C")
!
or
(1 2 (1 2) "a" "b" "C" "B" (2 3) 3)
result-list |a list .
Side Eects:
nunion is permitted to modify any part, car or cdr , of the list structure of list-1 or list-2 .
union and nunion return a list that contains every element that occurs in either list-1 or list-2 . Should be prepared to signal an error of type type-error if list-1 and list-2 are not proper lists .
For all possible ordered pairs consisting of one element from list-1 and one element from list-2 ,
:test or :test-not is used to determine whether they satisfy the test . The rst argument to the
See Also:
:test or :test-not function is the part of the element of list-1 extracted by the :key function (if
intersection, Section 3.2.1 (Compiler Terminology), Section 3.6 (Traversal Rules and Side Eects)
supplied); the second argument is the part of the element of list-2 extracted by the :key function
(if supplied). Notes:
The argument to the :key function is an element of list-1 or list-2 ; the return value is part of the The :test-not parameter is deprecated.
supplied element. If :key is not supplied or nil, the element of list-1 or list-2 itself is supplied to Since the nunion side eect is not required, it should not be used in for-eect-only positions in
the :test or :test-not function. portable code.
For every matching pair, one of the two elements of the pair will be in the result. Any element
from either list-1 or list-2 that matches no element of the other will appear in the result.
If there is a duplication between list-1 and list-2 , only one of the duplicate instances will be in
the result. If either list-1 or list-2 has duplicate entries within it, the redundant entries might or
might not appear in the result.
The order of elements in the result do not have to re ect the ordering of list-1 or list-2 in any
way. The result list may be eq to either list-1 or list-2 if appropriate.

Programming Language - Common Lisp 14. Conses

Uploaded by

Copyright:

Available Formats

Programming Language - Common Lisp 14. Conses

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Programming Language - Common Lisp 14. Conses

Uploaded by

Copyright:

Available Formats

Version 15.17, X3J13/94-101. Version 15.17, X3J13/94-101.

Wed 11-May-1994 6:57pm EDT Wed 11-May-1994 6:57pm EDT

Programming Language|Common Lisp

Conses i ii Programming Language|Common Lisp

14.1 Cons Concepts 14.1.2 Conses as Lists

Conses 14{1 14{2 Programming Language|Common Lisp

14.1.2.2 Lists as Sets list System Class

null System Class

Class Precedence List:

Conses 14{3 14{4 Programming Language|Common Lisp

cons System Class cons Function

Class Precedence List: Syntax:

Supertypes: consp Function

Conses 14{5 14{6 Programming Language|Common Lisp

The empty list is not a cons , so Function

(atom 'sss)! true

Conses 14{7 14{8 Programming Language|Common Lisp

cdddar, cddddr Accessor Arguments and Values:

Conses 14{9 14{10 Programming Language|Common Lisp

(cadr '(1 2)) !2

Conses 14{11 14{12 Programming Language|Common Lisp

Conses 14{13 14{14 Programming Language|Common Lisp

subst, subst-if, subst-if-not, nsubst, nsubst-if, :::

Arguments and Values: ! (SHAKESPEARE WROTE (THE TEMPEST))

Conses 14{15 14{16 Programming Language|Common Lisp

(subst-if 5 #'listp tree1) ! 5 Syntax:

Conses 14{17 14{18 Programming Language|Common Lisp

Conses 14{19 14{20 Programming Language|Common Lisp

Notes: (slow x (cdr slow))) ;Slow pointer: leaps by 1.

list-length list ! length ;; That fact justifies this implementation.)

length See Also:

Conses 14{21 14{22 Programming Language|Common Lisp

initial-element |an object . The default is nil. llst ! ((1))

Examples: Side E ects:

Conses 14{23 14{24 Programming Language|Common Lisp

rst, second, third, fourth, fth, sixth, seventh, :::

rst, second, third, fourth, fth, sixth, seventh, (first lst) 1 !

Conses 14{25 14{26 Programming Language|Common Lisp

See Also: Syntax:

Conses 14{27 14{28 Programming Language|Common Lisp

(null object )  (typep object 'null)  (eq object '())

(setq foo (list 'a 'b 'c 'd 'e)

Function baz (list 'k 'l 'm)) ! (K L M)

Conses 14{29 14{30 Programming Language|Common Lisp

See Also: (let ((list-1 '(1 2 3))

revappend list tail ! result-list

Conses 14{31 14{32 Programming Language|Common Lisp

Conses 14{33 14{34 Programming Language|Common Lisp

if n is not a non-negative integer . (format t "~2&list=~S ~21T(tailp object list)~

butlast, nth '(f g h) '() 'd 'x)))

ldi , tailp Function . list=(A B C . D)

Arguments and Values: ! NIL

list |a list , which might be a dotted list .

Conses 14{35 14{36 Programming Language|Common Lisp

(defun tailp (object list) Exceptional Situations:

Conses 14{37 14{38 Programming Language|Common Lisp

(rest '(1 . 2)) ! 2 Examples:

See Also: (member-if #'listp '(a b nil c d)) !

Examples: Side Eects:

(null object ) (typep object 'null) (eq object '())

ldi, tailp Function . list=(A B C . D)

The two expressions list-copy !((1 . "uno") (2 . "two"))

Arguments and Values: Side Eects:

set-dierence, nset-dierence