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.4, 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 by pointing to a distinguished value that is not a pair, represented in box-and-pointer diagrams as a diagonal line and in programs as the value of JavaScript's value null. The entire sequence is constructed by nested pair operations:
pair(1, pair(2, pair(3, pair(4, null))));
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. The result of pair(1, 2) is printed as [1, 2], and the data object in figure 2.4 is printed as [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);
tail(one_through_four);
head(tail(one_through_four));
pair(10, one_through_four);
pair(5, one_through_four);
The value null, used to terminate the chain of pairs, can be thought of as a sequence of no elements, the empty list.[2]
The use of pairs to represent sequences of elements as lists is accompanied
by conventional programming techniques for manipulating lists by
successively
tailing 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:
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);
Often we tail down the whole list. To aid in this, our JavaScript environment includes a 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)); }
The length function implements a simple recursive plan. The reduction step is:
We could also compute length in an iterative style:
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
pair up
an answer list while
tailing
down a list, as in the
function
append, which takes two lists as arguments and
combines their elements to make a new list:
append(squares, odds);
append(odds, squares);
The function append is also implemented using a recursive plan. To append lists list1 and list2, do the following:
function append(list1, list2) { return is_null(list1) ? list2 : pair(head(list1), append(tail(list1), list2)); }
last_pair(list(23, 72, 149, 34));
function last_pair(items) { return is_null(tail(items)) ? items : last_pair(tail(items)); }
reverse(list(1, 4, 9, 16, 25));
function reverse(items) { return is_null(items) ? null : append(reverse(tail(items)), pair(head(items), null)); }
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, 0.5);
cc(100, us_coins);
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); }
function plus_curried(x) { return y => x + y; }
brooks(plus_curried, list(3, 4));
brooks_curried(list(plus_curried, 3, 4));
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)); }
brooks_curried(list(brooks_curried, list(plus_curried, 3, 4)));
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)); }
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));
map(x => x * x, list(1, 2, 3, 4));
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.1, 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.
square_list(list(1, 2, 3, 4));
function square_list(items) { return is_null(items) ? null : pair(??, ??); }
function square_list(items) { return map(??, ??); }
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); }
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); }
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); }
for_each(x => display(x), list(57, 321, 88));
function for_each(fun, items) { if (is_null(items)){ return undefined; } else { fun(head(items)); for_each(fun, tail(items)); } }