Permalink copied!
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.8,
where the sequence 1, 2, 3, 4 is represented as a chain of pairs. The
head
of each pair is the
corresponding item in the chain, and the
tail
of the pair is the next pair in the chain. The
tail
of the final pair signals the end of the
sequence,
represented in box-and-pointer
diagrams as a diagonal line
and in programs as
JavaScript's primitive value
null.
The entire sequence is constructed by nested
pair
operations:
pair(1,
pair(2,
pair(3,
pair(4, null))));
Figure 2.8
The sequence 1, 2, 3, 4 represented as a chain of pairs.
Such a sequence of pairs, formed by nested
pair applications,
is called a
list, and
our 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).
In general,
list($a$$_{1}$, $a$$_{2}$, $\ldots$, $a$$_{n}$)
is equivalent to
pair($a$$_{1}$, pair($a$$_{2}$, pair($\ldots$, pair($a$$_{n}$, null)$\ldots$)))
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]]]]:
const one_through_four = list(1, 2, 3, 4);
one_through_four;
[1, [2, [3, [4, null]]]]
We can think of
head
as selecting the first item in the list, and of
tail
as selecting the sublist consisting of all but the first item. Nested
applications of
head
and
tail
can be used to extract the second, third, and subsequent items in the
list.
The constructor
pair
makes a list like the original one, but with an additional item at the
beginning.
head(one_through_four);
1
tail(one_through_four);
[2, [3, [4, null]]]
head(tail(one_through_four));
2
pair(10, one_through_four);
[10, [1, [2, [3, [4, null]]]]]
pair(5, one_through_four);
[5, [1, [2, [3, [4, null]]]]]
The value null, used to terminate
the chain of pairs, can be thought of as a sequence of no elements, the
empty list.
[2]
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.
[3]
The use of pairs to represent sequences of elements as lists is accompanied
by conventional programming techniques for manipulating lists by
successively
using tail to walk down the lists.
For example, the
function
list_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_ref
is the following:
- For $n=0$, list_ref should return the head of the list.
- Otherwise, list_ref should return the $(n-1)$st item of the tail of the list.
function list_ref(items, n) {
return n === 0
? head(items)
: list_ref(tail(items), n - 1);
}
const squares = list(1, 4, 9, 16, 25); list_ref(squares, 3);
16
Often we
walk down the whole list.
To aid in this,
our JavaScript environment
includes a primitive
predicate
is_null,
which tests whether its argument is the empty list. The
function
length, which returns the number of items in
a list, illustrates this typical pattern of use:
function length(items) {
return is_null(items)
? 0
: 1 + length(tail(items));
}
const odds = list(1, 3, 5, 7); length(odds);
4
The length
function
implements a simple recursive plan. The reduction step is:
- The length of any list is 1 plus the length of the tail of the list.
- The length of the empty list is 0.
function length(items) {
function length_iter(a, count) {
return is_null(a)
? count
: length_iter(tail(a), count + 1);
}
return length_iter(items, 0);
}
Another conventional programming technique is to
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
function
append, which takes two lists as arguments and
combines their elements to make a new list:
append(squares, odds);
list(1, 4, 9, 16, 25, 1, 3, 5, 7)
append(odds, squares);
list(1, 3, 5, 7, 1, 4, 9, 16, 25)
The function append
is also implemented using a recursive plan. To
append lists
list1 and list2,
do the following:
- If list1 is the empty list, then the result is just list2.
- Otherwise, append the tail of list1 and list2, and adjoin the head of list1 to the result:
function append(list1, list2) {
return is_null(list1)
? list2
: pair(head(list1), append(tail(list1), list2));
}
Define a
function
last_pair
that returns the list that contains only the last element of a given
(nonempty) list:
last_pair(list(23, 72, 149, 34));
list(34)
function last_pair(items) {
return is_null(tail(items))
? items
: last_pair(tail(items));
}
Define a
function
reverse that takes a list as argument and
returns a list of the same elements in reverse order:
reverse(list(1, 4, 9, 16, 25));
list(25, 16, 9, 4, 1)
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);
}
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
function
first_denomination
and partly into the
function
count_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
function
cc 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:
const us_coins = list(50, 25, 10, 5, 1); const uk_coins = list(100, 50, 20, 10, 5, 2, 1);
We could then call cc as follows:
cc(100, us_coins);
292
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:
function cc(amount, coin_values) {
return amount === 0
? 1
: amount < 0 || no_more(coin_values)
? 0
: cc(amount, except_first_denomination(coin_values)) +
cc(amount - first_denomination(coin_values), coin_values);
}
Define the
functions
first_denomination,
except_first_denomination,
and
no_more
in terms of primitive operations on list structures. Does the order of
the list
coin_values
affect the answer produced by cc?
Why or why not?
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.
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 -
brooks_curried(list(brooks_curried, list(brooks_curried, list(plus_curried, 3, 4))));
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
function
scales each number in a list by a given factor:
function scale_list(items, factor) {
return is_null(items)
? null
: pair(head(items) * factor,
scale_list(tail(items), factor));
}
scale_list(list(1, 2, 3, 4, 5), 10);
[10, [20, [30, [40, [50, null]]]]]
We can abstract this general idea and capture it as a common pattern
expressed as a higher-order
function,
just as in section 1.3. The
higher-order
function
here is called map.
The function map
takes as arguments a
function
of one argument and a list, and returns a list of the results produced by
applying the
function
to each element in the list:
function map(fun, items) {
return is_null(items)
? null
: pair(fun(head(items)),
map(fun, tail(items)));
}
map(abs, list(-10, 2.5, -11.6, 17));
[10, [2.5, [11.6, [17, null]]]]
map(x => x * x, list(1, 2, 3, 4));
[1, [4, [9, [16, null]]]]
Now we can give a new definition of
scale_list
in terms of map:
function scale_list(items, factor) {
return map(x => x * factor, items);
}
The 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,
the recursive structure of the program draws attention to the
element-by-element processing of the list. Defining
scale_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
functions
that transform lists from the details of how the elements of the list are
extracted and combined. Like the barriers shown in
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.
The
function
square_list
takes a list of numbers as argument and returns a list of the squares of
those numbers.
square_list(list(1, 2, 3, 4));
[1, [4, [9, [16, null]]]]
Here are two different definitions of
square_list.
Complete both of them by filling in the missing expressions:
function square_list(items) {
return is_null(items)
? null
: pair($\langle{}$??$\rangle$, $\langle{}$??$\rangle$);
}
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);
}
Louis Reasoner tries to rewrite the first
square_list
function
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(square(head(things)),
answer));
}
return iter(items, null);
}
Unfortunately, defining
square_list
this way produces the answer list in the reverse order of the one desired.
Why?
Louis then tries to fix his bug by interchanging the arguments to
pair:
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 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.
The
function
for_each
is similar to map. It takes as arguments a
function
and a list of elements. However, rather than forming a list of the
results,
for_each
just applies the
function
to each of the elements in turn, from left to right. The values returned by
applying the
function
to the elements are not used
at all—for_each
is used with
functions
that perform an action, such as printing. For example,
for_each(x => display(x), list(57, 321, 88));
57 321 88
The value returned by the call to
for_each
(not illustrated above) can be something arbitrary, such as true. Give an
implementation of
for_each.
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]
The value
null is used in JavaScript for
various purposes, but in this book we shall only use it to
represent the empty list.
[3]
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.
2.2.1
Representing Sequences