pair(1, pair(2, pair(3, pair(4, null))));
Such a sequence of pairs 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$)))
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); // result: 1
tail(one_through_four); // result: [2, [3, [4, null]]]
head(tail(one_through_four)); // result: 2
pair(10, one_through_four); // result: [10, [1, [2, [3, [4, null]]]]]
pair(5, one_through_four); // result: [5, [1, [2, [3, [4, null]]]]]
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); // result: 16
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);
// returns: [1, [4, [9, [16, [25, [1, [3, [5, [7, null]]]]]]]]]
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)); // result: [34, null]
function last_pair(items) { return is_null(tail(items)) ? items : last_pair(tail(items)); }
reverse(list(1, 4, 9, 16, 25)); // result: [25, [16, [9, [4, [1, null]]]]]
// naive reverse (what is the runtime?) 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, 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)); // returns: [1, [4, [9, [16, null]]]]
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)); } }