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.
Python's primitive value
None.
The entire sequence is constructed by nested
conspair
operations:
Original
Python
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
pair(1,
pair(2,
pair(3,
pair(4, None))))
Original
Python
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,
linked list,
and
Schemeour Python environment
provides a primitive called
listllist
to help in constructing
linked
lists.[1]
The above sequence could be produced by
(list 1 2 3 4).llist(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, None]]]]:
Original
Python
(define one-through-four (list 1 2 3 4))
one_through_four = llist(1, 2, 3, 4)
Original
Python
one-through-four
(1 2 3 4)
print(one_through_four)
[1, [2, [3, [4, None]]]]
Original
Python
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,linked list,
and of
cdrtail
as selecting the
sublistlinked-list component
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
listlinked list.[2]
The constructor
conspair
makes a
listlinked 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 None, used to terminate
the chain of pairs, can be thought of as a sequence of no elements, the
empty linked list.[4]
Original
Python
Box notation is sometimes difficult to read. In this book, when we want to
indicate the
linked-list nature of a data structure, we will employ the
alternative
linked-list notation: Whenever possible, linked-list notation uses
applications
of llist whose evaluation would result in the
desired structure. For example, instead of the box notation
[1, [[2, 3], [[4, [5, None]], [6, None]]]]
we write
llist(1, [2, 3], llist(4, 5), 6)
in linked-list notation.[5]
ListLinked-list
operations
The use of pairs to represent sequences of elements as
listslinked lists
is accompanied
by conventional programming techniques for manipulating
listslinked lists
by
successively
cdring down
the lists.
using tail to walk down the
linked lists.
For example, the
procedurefunctionlist-refref
takes as arguments a
listlinked list
and a number $n$ and
returns the $n$th item of the
list.linked list.
It is
customary to number the elements of the
listlinked list
beginning with 0. The method
for computing
list-refref
is the following:
For $n=0$,
list-refref
should return the
carhead
of the
list.linked list.
Otherwise,
list-refref
should return the $(n-1)$st item of the
cdrtail
of the
list.linked list.
Original
Python
(define (list-ref items n)
(if (= n 0)
(car items)
(list-ref (cdr items) (- n 1))))
def ref(items, n):
return (head(items) if n == 0
else ref(tail(items), n - 1))
Often we
cdr down the whole list.
walk down the whole linked list.
To aid in this,
Schemeour Python environment
includes a primitive
predicate
null?,is_none,
which tests whether its argument is the empty
list.linked list.
The
procedurefunctionlength, which returns the number of items in a
list,linked 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
linked list
by adjoining elements to
the front of the linked list with
pair
while walking down a linked list using
tail,
as in the
procedurefunctionappend, which takes two
lists as arguments and
combines their elements to make a new list:
append,
which takes two linked lists as arguments and
combines their elements to make a new linked list:
AppendThe function append
is also implemented using a recursive plan.
To
append
lists
list1 and
list2,
do the following:
To append
linked lists
list1 and
list2,
do the following:
If list1 is the empty
list,
linked list,
then the
result is just list2.
Otherwise,
append the
cdr
of list1 and
list2, and
cons
the
car
of list1
onto the result:
append the
tail
of list1 and
list2, and
adjoin
the
head
of list1
to the result:
Exercise 2.17
Define a
procedurefunctionlast-pairlast_pair
that returns the
list
linked list
that contains only the last element of a given
(nonempty)
list:
linked list:
def last_pair(items):
return (items if is_none(tail(items))
else last_pair(tail(items)))
Exercise 2.18
Define a
procedurefunctionreversereverse
that takes a
listlinked list
as argument and
returns a
listlinked list
of the same elements in reverse order:
Naive reverse (what is the run time?):
def reverse(items):
return (None if is_none(items)
else append(reverse(tail(items)),
pair(head(items), None)))
A better version:
def reverse(items):
def reverse_iter(items, result):
return (result if is_none(items)
else reverse_iter(tail(items),
pair(head(items), result)))
return reverse_iter(items, None)
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
listlinked list
of coins to be used for making change.
We want to rewrite the
procedurefunctioncc so that its second argument
is a
listlinked list
of
the values of the coins to use rather than an integer specifying which
coins to use. We could then have
listslinked 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:
def cc(amount, coin_values):
return (1 if amount == 0
else 0 if amount < 0 or no_more(coin_values)
else cc(amount, except_first_denomination(coin_values)) +
cc(amount - first_denomination(coin_values), coin_values))
Define the
proceduresfunctionsfirst-denomination,first_denomination,
except-first-denomination,except_first_denomination,
and
no-more?no_more
in terms of primitive operations on
listlinked list
structures. Does the order of
the
listlinked listcoin-valuescoin_values
affect the answer produced by cc?
Why or why not?
The order of the
listlinked listcoin_values
does not affect the answer given by any correct solution of the problem,
because the given
listlinked list
represents an unordered collection of
denominations.
Original
Python
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 Python, a curried
version of plus looks as follows.
def plus_curried(x):
return lambda y: x + y
Write a function brooks that
takes a curried function as first argument and as second argument a linked 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):
print(brooks(plus_curried, llist(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:
print(brooks_curried(llist(plus_curried, 3, 4)))
7
With this function brooks_curried,
what are the results of evaluating the following two statements?
brooks_curried(llist(brooks_curried,
llist(plus_curried, 3, 4)))
brooks_curried(llist(brooks_curried,
llist(brooks_curried,
llist(plus_curried, 3, 4))))
def brooks(f, items):
return (f if is_none(items)
else brooks(f(head(items)), tail(items)))
One extremely useful operation is to apply some transformation to each
element in a
list
linked list
and generate the
list
linked list
of results. For instance, the
following
procedurefunction
scales each number in a
list
linked 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 mapmap.
MapThe function map
takes as arguments a
procedurefunction
of one argument and a
list,
linked list,
and returns a
list
linked list
of the results produced by
applying the
procedurefunction
to each element in the
list:[6]linked list:
def scale_linked_list(items, factor):
return map(lambda 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.
linked lists.
In the original definition of
scale-list,scale_linked_list,
the recursive structure of the program draws attention to the
element-by-element processing of the
list.
linked list.
Defining
scale-listscale_linked_list
in terms of
mapmap
suppresses that level of
detail and emphasizes that scaling transforms a
list
linked list
of elements to a
list
linked 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,
mapmap
helps establish an abstraction barrier
that isolates the implementation of
proceduresfunctions
that transform listslinked lists from the details of how the elements of the listlinked 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_linked_list
takes a
listlinked list
of numbers as argument and returns a
listlinked list
of the squares of
those numbers.
Original
Python
;; square-list to be given by student
(square-list (list 1 2 3 4))
(1 4 9 16)
Exercise 2.22
Louis Reasoner tries to rewrite the first
square-listsquare_linked_listprocedurefunction
of exercise 2.21 so that it evolves an
iterative process:
The result
listlinked list
is reversed in the first program because the argument
listlinked list
is traversed in the given order, from first to last, but squares
are added successively to the front of the answer
listlinked list
via
cons.pair.
The last element of the
listlinked list
is the last one to be added to the answer
and thus ends up as the first element of the result
list.linked list.
The second program makes things worse! The result is not even a
listlinked list
any longer, because the elements occupy the tail position of the
result and not the head position.
Exercise 2.23
The
procedurefunctionfor-eachfor_each
is similar to
mapmap
It takes as arguments a
procedurefunction
and a
listlinked list
of elements. However, rather than forming a
listlinked 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.
[1]
In this book, we use
listlinked list
to mean a chain of
pairs terminated by the end-of-list markerend-of-linked-list marker.
In contrast, the term
list structurelinked-list structure
refers to any data structure made out of pairs,
not just to
lists.linked 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
None is used in Python for
various purposes, as we shall see in chapter 3.
[5]
Our Python environment provides
a primitive function
print_llist
that works like the primitive function
print, except that
it uses linked-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))
