One of the useful structures we can build with pairs is a
sequence—an ordered collection of data objects. There
are, of course, many ways to represent sequences in terms of pairs. One
particularly straightforward representation is illustrated in
figure 2.7,figure 2.8,
where the sequence 1, 2, 3, 4 is represented as a chain of pairs. The
carhead
of each pair is the
corresponding item in the chain, and the
cdrtail
of the pair is the next pair in the chain. The
cdrtail
of the final pair signals the end of the
sequence by pointing to a
distinguished value that is not a pair,
sequence,
represented in box-and-pointer
diagrams as a diagonal line
and in programs as
the value of the variable nil.
JavaScript's primitive value
null.
The entire sequence is constructed by nested
conspair
operations:
Original
JavaScript
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
pair(1,
pair(2,
pair(3,
pair(4, null))));
Original
JavaScript
Figure 2.7 The sequence 1, 2, 3, 4 represented as a chain of pairs.
Figure 2.8 The sequence 1, 2, 3, 4 represented as a chain of pairs.
Such a sequence of pairs, formed by nested
conses,
pair applications,
is called a
list, and
Schemeour JavaScript environment
provides a primitive called
list to help in constructing
lists.[1]
The above sequence could be produced by
(list 1 2 3 4).list(1, 2, 3, 4).
In general,
Lisp systems conventionally print lists by printing the sequence of
elements, enclosed in parentheses. Thus, the data object in
figure 2.7
is printed as
(1 2 3 4):
Our interpreter prints pairs using a textual representation of
box-and-pointer diagrams that we call box notation.
The result of pair(1, 2)
is printed as [1, 2], and
the data object in figure 2.8
is printed as
[1, [2, [3, [4, null]]]]:
Original
JavaScript
(define one-through-four (list 1 2 3 4))
const one_through_four = list(1, 2, 3, 4);
Original
JavaScript
one-through-four
(1 2 3 4)
one_through_four;
[1, [2, [3, [4, null]]]]
Original
JavaScript
Be careful not to confuse the expression
(list 1 2 3 4) with the list
(1 2 3 4), which is the result obtained
when the expression is evaluated. Attempting to evaluate the
expression (1 2 3 4) will signal an error
when the interpreter tries to apply the procedure
1 to arguments
2, 3,
and 4.
We can think of
carhead
as selecting the first item in the list, and of
cdrtail
as selecting the sublist consisting of all but the first item. Nested
applications of
carhead
and
cdrtail
can be used to extract the second, third, and subsequent items in the
list.[2]
The constructor
conspair
makes a list like the original one, but with an additional item at the
beginning.
The value of nil, used to terminate the
chain of pairs, can be thought of as a sequence of no elements, the
empty list. The word nil is a contraction of the
Latin word nihil, which means
nothing.[3]
The value null, used to terminate
the chain of pairs, can be thought of as a sequence of no elements, the
empty list.[4]
Original
JavaScript
Box notation is sometimes difficult to read. In this book, when we want to
indicate the list nature of a data structure, we will employ the
alternative
list notation: Whenever possible, list notation uses
applications
of list whose evaluation would result in the
desired structure. For example, instead of the box notation
[1, [[2, 3], [[4, [5, null]], [6, null]]]]
we write
list(1, [2, 3], list(4, 5), 6)
in list notation.[5]
List operations
The use of pairs to represent sequences of elements as lists is accompanied
by conventional programming techniques for manipulating lists by
successively
cdring down
the lists.
using tail to walk down the lists.
For example, the
procedurefunctionlist-reflist_ref
takes as arguments a list and a number $n$ and
returns the $n$th item of the list. It is
customary to number the elements of the list beginning with 0. The method
for computing
list-reflist_ref
is the following:
For $n=0$,
list-reflist_ref
should return the
carhead
of the list.
Otherwise,
list-reflist_ref
should return the $(n-1)$st item of the
cdrtail
of the list.
Original
JavaScript
(define (list-ref items n)
(if (= n 0)
(car items)
(list-ref (cdr items) (- n 1))))
function list_ref(items, n) {
return n === 0
? head(items)
: list_ref(tail(items), n - 1);
}
Often we
cdr down the whole list.
walk down the whole list.
To aid in this,
Schemeour JavaScript environment
includes a primitive
predicate
null?,is_null,
which tests whether its argument is the empty list. The
procedurefunctionlength, which returns the number of items in
a list, illustrates this typical pattern of use:
Another conventional programming technique is to
cons up
the heads and tails of an answer list while
cdring down a list,
construct an answer list by adjoining elements to
the front of the list with
pair
while walking down a list using
tail,
as in the
procedurefunctionappend, which takes two lists as arguments and
combines their elements to make a new list:
Naive reverse (what is the run time?):
function reverse(items) {
return is_null(items)
? null
: append(reverse(tail(items)),
pair(head(items), null));
}
A better version:
function reverse(items) {
function reverse_iter(items, result) {
return is_null(items)
? result
: reverse_iter(tail(items),
pair(head(items), result));
}
return reverse_iter(items, null);
}
Exercise 2.19
Consider the
change-counting program of
section 1.2.2. It would be nice to be
able to easily change the currency used by the program, so that we could
compute the number of ways to change a British pound, for example. As
the program is written, the knowledge of the currency is distributed
partly into the
procedurefunctionfirst-denominationfirst_denomination
and partly into the
procedurefunctioncount-changecount_change
(which knows
that there are five kinds of U.S. coins).
It would be nicer
to be able to supply a list of coins to be used for making change.
We want to rewrite the
procedurefunctioncc so that its second argument is a list of
the values of the coins to use rather than an integer specifying which
coins to use. We could then have lists that defined each kind of
currency:
To do this will require changing the program
cc somewhat. It will still have the same
form, but it will access its second argument differently, as follows:
Define the
proceduresfunctionsfirst-denomination,first_denomination,
except-first-denomination,except_first_denomination,
and
no-more?no_more
in terms of primitive operations on list structures. Does the order of
the list
coin-valuescoin_values
affect the answer produced by cc?
Why or why not?
Original
JavaScript
function first_denomination(coin_values) {
return head(coin_values);
}
function except_first_denomination(coin_values) {
return tail(coin_values);
}
function no_more(coin_values) {
return is_null(coin_values);
}
The order of the list coin_values
does not affect the answer given by any correct solution of the problem,
because the given list represents an unordered collection of
denominations.
Original
JavaScript
Exercise 2.20
In the presence of higher-order functions, it is not strictly necessary
for functions to have multiple parameters; one would
suffice. If we have a function such as
plus that naturally requires two
arguments, we could write a variant of the function to which we pass
the arguments one at a time. An application of the variant to the
first argument could return a function that we can then apply to the
second argument, and so on. This practice—called
currying and named after the American mathematician and
logician
Haskell Brooks Curry—is quite common in programming
languages such as
Haskell and
OCaml. In JavaScript, a curried
version of plus looks as follows.
function plus_curried(x) {
return y => x + y;
}
Write a function brooks that
takes a curried function as first argument and as second argument a list
of arguments to which the curried function is then applied, one by one,
in the given order. For example, the following application of
brooks should have the
same effect as
plus_curried(3)(4):
brooks(plus_curried, list(3, 4));
7
While we are at it, we might as well curry the function
brooks! Write a function
brooks_curried that can be applied
as follows:
brooks_curried(list(plus_curried, 3, 4));
7
With this function brooks_curried,
what are the results of evaluating the following two statements?
brooks_curried(list(brooks_curried,
list(plus_curried, 3, 4)));
brooks_curried(list(brooks_curried,
list(brooks_curried,
list(plus_curried, 3, 4))));
function brooks(f, items) {
return is_null(items)
? f
: brooks(f(head(items)), tail(items));
}
function brooks_curried(items) {
return brooks(head(items), tail(items));
}
The statement
brooks_curried(list(brooks_curried,
list(plus_curried, 3, 4)));
of course evaluates to 7, as does
One extremely useful operation is to apply some transformation to each
element in a list and generate the list of results. For instance, the
following
procedurefunction
scales each number in a list by a given factor:
We can abstract this general idea and capture it as a common pattern
expressed as a higher-order
procedure,function,
just as in section 1.3. The
higher-order
procedurefunction
here is called map.
MapThe function map
takes as arguments a
procedurefunction
of one argument and a list, and returns a list of the results produced by
applying the
procedurefunction
to each element in the list:[6]
function scale_list(items, factor) {
return map(x => x * factor, items);
}
MapThe function map
is an important construct, not only because it captures a common pattern,
but because it establishes a higher level of abstraction in dealing with
lists. In the original definition of
scale-list,scale_list,
the recursive structure of the program draws attention to the
element-by-element processing of the list. Defining
scale-listscale_list
in terms of map suppresses that level of
detail and emphasizes that scaling transforms a list of elements to a list
of results. The difference between the two definitions is not that the
computer is performing a different process (it isn't) but that we
think about the process differently. In effect,
map helps establish an abstraction barrier
that isolates the implementation of
proceduresfunctions
that transform lists from the details of how the elements of the list are
extracted and combined. Like the barriers shown in
figure 2.1,
figure 2.2,
this abstraction gives us the flexibility to change the low-level details
of how sequences are implemented, while preserving the conceptual framework
of operations that transform sequences to sequences.
Section 2.2.3 expands
on this use of sequences as a framework for organizing programs.
Exercise 2.21
The
procedurefunctionsquare-listsquare_list
takes a list of numbers as argument and returns a list of the squares of
those numbers.
Original
JavaScript
;; square-list to be given by student
(square-list (list 1 2 3 4))
(1 4 9 16)
function square_list(items) {
return map($\langle{}$??$\rangle$, $\langle{}$??$\rangle$);
}
function square_list(items) {
return is_null(items)
? null
: pair(square(head(items)),
square_list(tail(items)));
}
function square_list(items) {
return map(square, items);
}
Exercise 2.22
Louis Reasoner tries to rewrite the first
square-listsquare_listprocedurefunction
of exercise 2.21 so that it evolves an
iterative process:
function square_list(items) {
function iter(things, answer) {
return is_null(things)
? answer
: iter(tail(things),
pair(answer,
square(head(things))));
}
return iter(items, null);
}
This doesn't work either. Explain.
The result list is reversed in the first program because the argument
list is traversed in the given order, from first to last, but squares
are added successively to the front of the answer list via
cons.pair.
The last element of the list is the last one to be added to the answer
and thus ends up as the first element of the result list.
The second program makes things worse! The result is not even a list
any longer, because the elements occupy the tail position of the
result list and not the head position.
Exercise 2.23
The
procedurefunctionfor-eachfor_each
is similar to map. It takes as arguments a
procedurefunction
and a list of elements. However, rather than forming a list of the
results,
for-eachfor_each
just applies the
procedurefunction
to each of the elements in turn, from left to right. The values returned by
applying the
procedurefunction
to the elements are not used
at all—for-eachat all—for_each
is used with
proceduresfunctions
that perform an action, such as printing. For example,
The value returned by the call to
for-eachfor_each
(not illustrated above) can be something arbitrary, such as true. Give an
implementation of
for-each.for_each.
Original
JavaScript
function for_each(fun, items) {
if (is_null(items)){
return undefined;
} else {
fun(head(items));
for_each(fun, tail(items));
}
}
[1]
In this book, we use list to mean a chain of
pairs terminated by the end-of-list marker. In contrast, the term
list structure refers to any data structure made out of pairs,
not just to lists.
[2]
Since nested applications of
car and cdr are
cumbersome to write, Lisp dialects provide abbreviations for
them—for instance,
(cadr $\langle arg \rangle$) = (car (cdr $\langle arg \rangle$))
The names of all such procedures start with c
and end with r. Each
a between them stands for a
car operation and each
d for a cdr
operation, to be applied in the same order in which they appear in the
name. The names car and
cdr persist because simple combinations like
cadr are
pronounceable.
[3]
It's remarkable how much energy
in the standardization of Lisp dialects has been dissipated in
arguments that are literally over nothing: Should
nil be an ordinary name? Should the value
of nil be a symbol? Should it be a list?
Should it be a pair?
In Scheme, nil is an ordinary name, which
we use in this section as a variable whose value is the end-of-list
marker (just as true is an ordinary
variable that has a true value). Other dialects of Lisp, including
Common Lisp, treat nil as a special
symbol. The
authors of this book, who have endured too many language
standardization brawls, would like to avoid the entire issue. Once we
have introduced quotation in
section 2.3, we will denote the
empty list as '() and dispense with the
variable nil entirely.
[4]
The value
null is used in JavaScript for
various purposes, but in this book we shall only use it to
represent the empty list.
[5]
Our JavaScript environment provides
a primitive function
display_list
that works like the primitive function
display, except that
it uses list notation instead of box notation.
[6]
Scheme standardly provides a
map
procedure that is more general than the one described here. This more
general map takes a procedure of
$n$ arguments, together with
$n$ lists, and applies the procedure to all the
first elements of the lists, all the second elements of the lists, and so
on, returning a list of the results. For example:
(map + (list 1 2 3) (list 40 50 60) (list 700 800 900))
(741 852 963)
(map (lambda (x y) (+ x (* 2 y)))
(list 1 2 3)
(list 4 5 6))
