In Lisp, a list looks like this: '(rose violet daisy buttercup). This list is preceded by a single apostrophe. It could just as well be written as follows, which looks more like the kind of list you are likely to be familiar with:
A D V E R T I S E M E N T
Lists are containers that supports sequential traversal. List is also a
recursive data structure: its definition is recursive. As such, most of its
traversal algorithms are recursive functions. In order to better understand a
recursive abstract data type and prepare oneself to develop recursive operations
on the data type, one should present the data type in terms of its
constructors, selectors and recognizers.
Constructors are forms that create new instances of a data type (possibly out
of some simpler components). A list is obtained by evaluating one of the
following constructors:
nil: Evaluating nil creates an empty list;
(cons xL): Given a LISP object x
and a list L, evaluating (cons xL)
creates a list containing x followed by the elements in L.
Notice that the above definition is inherently recursive. For example, to
construct a list containing 1 followed by 2, we could type in the expression:
USER(21): (cons 1 (cons 2 nil))
(1 2)
LISP replies by printing (1 2), which is a more readable representation
of a list containing 1 followed by 2. To understand why the above works, notice
that nil is a list (an empty one), and thus (cons 2 nil) is
also a list (a list containing 1 followed by nothing). Applying the second
constructor again, we see that (cons 1 (cons 2 nil)) is also a list (a
list containing 1 followed by 2 followed by nothing).
Typing cons expressions could be tedious. If we already know all the
elements in a list, we could enter our list as list literals. For
example, to enter a list containing all prime numbers less than 20, we could
type in the following expression:
Notice that we have quoted the list using the quote special form. This
is necessary because, without the quote, LISP would interpret the expression
(2 3 5 7 11 13 17 19) as a function call to a function with name "2" and
arguments 3, 5, ..., 19 The quote is just a syntactic device that
instructs LISP not to evaluate the a form in applicative order, but rather treat
it as a literal. Since quoting is used frequently in LISP programs, there is a
shorthand for quote:
The quote symbol ' is nothing but a syntactic shorthand for (quote
...).
The second ingredient of an abstract data type are its selectors. Given a
composite object constructed out of several components, a selector form returns
one of its components. Specifically, suppose a list L1 is
constructed by evaluating (cons xL2),
where x is a LISP object and L2 is a list. Then,
the selector forms (first L1) and (rest L1)
evaluate to x and L2 respectively, as the following
examples illustrate:
Finally, we look at recognizers, expressions that test how an object is
constructed. Corresponding to each constructor of a data type is a recognizer.
In the case of list, they are null for nil and consp
for cons. Given a list L, (null L) returns
t iff L is nil, and (consp L)
returns t iff L is constructed from cons.
USER(29): (null nil)
T
USER(30): (null '(1 2 3))
NIL
USER(31): (consp nil)
NIL
USER(32): (consp '(1 2 3))
T
