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 car head of each pair is the corresponding item in the chain, and the cdr tail of the pair is the next pair in the chain. The cdr tail of the final pair signals the end of the sequence by pointing to a distinguished value that is not a pair, sequence, represented in boxandpointer 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 cons pair operations:
Original  JavaScript 
(cons 1 (cons 2 (cons 3 (cons 4 nil))))  pair(1, pair(2, pair(3, pair(4, null)))); 
Original  JavaScript  
Such a sequence of pairs, formed by nested conses, pair applications, is called a list, and Scheme 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). list(1, 2, 3, 4). In general,
Original  JavaScript 
(list a$_{1}$ a$_{2}$ $\ldots$ a$_{n}$)  list($a$$_{1}$, $a$$_{2}$, $\ldots$, $a$$_{n}$) 
Original  JavaScript 
(cons a$_{1}$ (cons a$_{2}$ (cons $\ldots$ (cons a$_{n}$ nil) $\ldots$)))  pair($a$$_{1}$, pair($a$$_{2}$, pair($\ldots$, pair($a$$_{n}$, null)$\ldots$))) 
Original  JavaScript  
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 boxandpointer 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 onethroughfour (list 1 2 3 4))  const one_through_four = list(1, 2, 3, 4); 
Original  JavaScript 
onethroughfour (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 car head as selecting the first item in the list, and of cdr tail as selecting the sublist consisting of all but the first item. Nested applications of car head and cdr tail can be used to extract the second, third, and subsequent items in the list.[2] The constructor cons pair makes a list like the original one, but with an additional item at the beginning.
Original  JavaScript 
(car onethroughfour) 1  head(one_through_four); 1 
Original  JavaScript 
(cdr onethroughfour) (2 3 4)  tail(one_through_four); [2, [3, [4, null]]] 
Original  JavaScript 
(car (cdr onethroughfour)) 2  head(tail(one_through_four)); 2 
Original  JavaScript 
(cons 10 onethroughfour) (10 1 2 3 4)  pair(10, one_through_four); [10, [1, [2, [3, [4, null]]]]] 
Original  JavaScript 
(cons 5 onethroughfour) (5 1 2 3 4)  pair(5, one_through_four); [5, [1, [2, [3, [4, null]]]]] 
Original  JavaScript  
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] 
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
procedure
function
listref
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
listref
list_ref
is the following:
Original  JavaScript 
(define (listref items n) (if (= n 0) (car items) (listref (cdr items) ( n 1))))  function list_ref(items, n) { return n === 0 ? head(items) : list_ref(tail(items), n  1); } 
Original  JavaScript 
(define squares (list 1 4 9 16 25)) (listref squares 3) 16  const squares = list(1, 4, 9, 16, 25); list_ref(squares, 3); 16 
Often we cdr down the whole list. walk down the whole list. To aid in this, Scheme our JavaScript environment includes a primitive predicate null?, is_null, which tests whether its argument is the empty list. The procedure function length, which returns the number of items in a list, illustrates this typical pattern of use:
Original  JavaScript 
(define (length items) (if (null? items) 0 (+ 1 (length (cdr items)))))  function length(items) { return is_null(items) ? 0 : 1 + length(tail(items)); } 
Original  JavaScript 
(define odds (list 1 3 5 7)) (length odds)  const odds = list(1, 3, 5, 7); length(odds); 4 
Original  JavaScript 
(define (length items) (define (lengthiter a count) (if (null? a) count (lengthiter (cdr a) (+ 1 count)))) (lengthiter items 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
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
procedure
function
append, which takes two lists as arguments and
combines their elements to make a new list:
Original  JavaScript 
(append squares odds) (1 4 9 16 25 1 3 5 7)  append(squares, odds); list(1, 4, 9, 16, 25, 1, 3, 5, 7) 
Original  JavaScript 
(append odds squares) (1 3 5 7 1 4 9 16 25)  append(odds, squares); list(1, 3, 5, 7, 1, 4, 9, 16, 25) 
Original  JavaScript 
(define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2))))  function append(list1, list2) { return is_null(list1) ? list2 : pair(head(list1), append(tail(list1), list2)); } 
Original  JavaScript 
(lastpair (list 23 72 149 34)) (34)  last_pair(list(23, 72, 149, 34)); list(34) 
Original  JavaScript 
function last_pair(items) { return is_null(tail(items)) ? items : last_pair(tail(items)); } 
Original  JavaScript 
(reverse (list 1 4 9 16 25)) (25 16 9 4 1)  reverse(list(1, 4, 9, 16, 25)); list(25, 16, 9, 4, 1) 
We want to rewrite the procedure 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:
Original  JavaScript 
(define uscoins (list 50 25 10 5 1)) (define ukcoins (list 100 50 20 10 5 2 1))  const us_coins = list(50, 25, 10, 5, 1); const uk_coins = list(100, 50, 20, 10, 5, 2, 1); 
Original  JavaScript 
(cc 100 uscoins) 292  cc(100, us_coins); 292 
Original  JavaScript 
(define (cc amount coinvalues) (cond ((= amount 0) 1) ((or (< amount 0) (nomore? coinvalues)) 0) (else (+ (cc amount (exceptfirstdenomination coinvalues)) (cc ( amount (firstdenomination coinvalues)) coinvalues)))))  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); } 
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); } 
Original  JavaScript  
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.


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 procedure function scales each number in a list by a given factor:
Original  JavaScript 
(define (scalelist items factor) (if (null? items) nil (cons (* (car items) factor) (scalelist (cdr items) factor))))  function scale_list(items, factor) { return is_null(items) ? null : pair(head(items) * factor, scale_list(tail(items), factor)); } 
Original  JavaScript 
(scalelist (list 1 2 3 4 5) 10) (10 20 30 40 50)  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 higherorder procedure, function, just as in section 1.3. The higherorder procedure function here is called map. Map The function map takes as arguments a procedure function of one argument and a list, and returns a list of the results produced by applying the procedure function to each element in the list:[7]
Original  JavaScript 
(define (map proc items) (if (null? items) nil (cons (proc (car items)) (map proc (cdr items)))))  function map(fun, items) { return is_null(items) ? null : pair(fun(head(items)), map(fun, tail(items))); } 
Original  JavaScript 
(map abs (list 10 2.5 11.6 17)) (10 2.5 11.6 17)  map(abs, list(10, 2.5, 11.6, 17)); [10, [2.5, [11.6, [17, null]]]] 
Original  JavaScript 
(map (lambda (x) (* x x)) (list 1 2 3 4)) (1 4 9 16)  map(x => x * x, list(1, 2, 3, 4)); [1, [4, [9, [16, null]]]] 
Original  JavaScript 
(define (scalelist items factor) (map (lambda (x) (* x factor)) items))  function scale_list(items, factor) { return map(x => x * factor, items); } 
Map 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 scalelist, scale_list, the recursive structure of the program draws attention to the elementbyelement processing of the list. Defining scalelist 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 procedures 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, figure 2.2, this abstraction gives us the flexibility to change the lowlevel 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.
Original  JavaScript 
;; squarelist to be given by student (squarelist (list 1 2 3 4)) (1 4 9 16)  square_list(list(1, 2, 3, 4)); [1, [4, [9, [16, null]]]] 
Original  JavaScript 
(define (squarelist items) (if (null? items) nil (cons ?? ??)))  function square_list(items) { return is_null(items) ? null : pair($\langle{}$??$\rangle$, $\langle{}$??$\rangle$); } 
Original  JavaScript 
(define (squarelist items) (map ?? ??))  function square_list(items) { return map($\langle{}$??$\rangle$, $\langle{}$??$\rangle$); } 
Original  JavaScript 
(define (squarelist items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons (square (car things)) answer)))) (iter items nil))  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); } 
Louis then tries to fix his bug by interchanging the arguments to cons: pair:
Original  JavaScript 
(define (squarelist items) (define (iter things answer) (if (null? things) answer (iter (cdr things) (cons answer (square (car things)))))) (iter items nil))  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); } 
Original  JavaScript 
(foreach (lambda (x) (newline) (display x)) (list 57 321 88)) 57 321 88  for_each(x => display(x), list(57, 321, 88)); 57 321 88 
Original  JavaScript 
function for_each(fun, items) { if (is_null(items)){ return undefined; } else { fun(head(items)); for_each(fun, tail(items)); } } 