Contents|Symbol Index|Prev: 13. Characters|Next: 15. Arrays

14. Conses

14.1 Cons Concepts
Dictionary

14.1 Cons Concepts#

A cons is a compound data object having two components called the car and the cdr.

`car`	`cons`	`rplacd`
`cdr`	`rplaca`

Figure 14–1. Some defined names relating to conses.

Depending on context, a group of connected conses can be viewed in a variety of different ways. A variety of operations is provided to support each of these various views.

14.1.1 Conses as Trees#

A tree is a binary recursive data structure made up of conses and atoms: the conses are themselves also trees (sometimes called “subtrees” or “branches”), and the atoms are terminal nodes (sometimes called leaves). Typically, the leaves represent data while the branches establish some relationship among that data.

`caaaar`	`caddar`	`cdar`	`nsubst`
`caaadr`	`cadddr`	`cddaar`	`nsubst-if`
`caaar`	`caddr`	`cddadr`	`nsubst-if-not`
`caadar`	`cadr`	`cddar`	`nthcdr`
`caaddr`	`cdaaar`	`cdddar`	`sublis`
`caadr`	`cdaadr`	`cddddr`	`subst`
`caar`	`cdaar`	`cdddr`	`subst-if`
`cadaar`	`cdadar`	`cddr`	`subst-if-not`
`cadadr`	`cdaddr`	`copy-tree`	`tree-equal`
`cadar`	`cdadr`	`nsublis`

Figure 14–2. Some defined names relating to trees.

14.1.1.1 General Restrictions on Parameters that must be Trees#

Except as explicitly stated otherwise, for any standardized function that takes a parameter that is required to be a tree, the consequences are undefined if that tree is circular.

14.1.2 Conses as Lists#

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.

A proper list is a list terminated by the empty list. The empty list is a proper list, but is not a cons.

An improper list is a list that is not a proper list; that is, it is a circular list or a dotted list.

A dotted list is a list that has a terminating atom that is not the empty list. A non-nil atom by 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 cdr of a later cons.

`append`	`last`	`nbutlast`	`rest`
`butlast`	`ldiff`	`nconc`	`revappend`
`copy-alist`	`list`	`ninth`	`second`
`copy-list`	`list*`	`nreconc`	`seventh`
`eighth`	`list-length`	`nth`	`sixth`
`endp`	`make-list`	`nthcdr`	`tailp`
`fifth`	`member`	`pop`	`tenth`
`first`	`member-if`	`push`	`third`
`fourth`	`member-if-not`	`pushnew`

Figure 14–3. Some defined names relating to lists.

14.1.2.1 Lists as Association Lists#

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`
`assoc`	`assoc-if-not`	`rassoc`	`rassoc-if-not`

Figure 14–4. Some defined names related to assocation lists.

14.1.2.2 Lists as Sets#

Lists are sometimes viewed as sets by considering their elements unordered and by assuming there is no duplication of elements.

`adjoin`	`nset-difference`	`set-difference`	`union`
`intersection`	`nset-exclusive-or`	`set-exclusive-or`
`nintersection`	`nunion`	`subsetp`

Figure 14–5. Some defined names related to sets.

14.1.2.3 General Restrictions on Parameters that must be Lists#

Except as explicitly specified otherwise, any standardized function that takes a parameter that is required to be a list should be prepared to signal an error of type type-error if the value received is a dotted list.

Sandra complained that this was only said a few places, and needed to be said more. This is a stopgap while we make sure we mean it everywhere.Except as explicitly specified otherwise, for any standardized function that takes a parameter that is required to be a list, the consequences are undefined if that list is circular.

Dictionary

list System Class
null System Class
cons System Class
atom Type
cons Function
consp Function
atom Function
rplaca, rplacd Function
car, cdr, caar, cadr, cdar, cddr, caaar, caadr, cadar, caddr, cdaar, cdadr, cddar, cdddr, caaaar, caaadr, caadar, caaddr, cadaar, cadadr, caddar, cadddr, cdaaar, cdaadr, cdadar, cdaddr, cddaar, cddadr, cdddar, cddddr Accessor
copy-tree Function
sublis, nsublis Function
subst, subst-if, subst-if-not, nsubst, nsubst-if, nsubst-if-not Function
tree-equal Function
copy-list Function
list, list* Function
list-length Function
listp Function
make-list Function
push Macro
pop Macro
first, second, third, fourth, fifth, sixth, seventh, eighth, ninth, tenth Accessor
nth Accessor
endp Function
null Function
nconc Function
append Function
revappend, nreconc Function
butlast, nbutlast Function
last Function
ldiff, tailp Function
nthcdr Function
rest Accessor
member, member-if, member-if-not Function
mapc, mapcar, mapcan, mapl, maplist, mapcon Function
acons Function
assoc, assoc-if, assoc-if-not Function
copy-alist Function
pairlis Function
rassoc, rassoc-if, rassoc-if-not Function
get-properties Function
getf Accessor
remf Macro
intersection, nintersection Function
adjoin Function
pushnew Macro
set-difference, nset-difference Function
set-exclusive-or, nset-exclusive-or Function
subsetp Function
union, nunion Function

Contents|Symbol Index|Prev: 13. Characters|Next: 15. Arrays