2.2.1 Representing Sequences - SICP Comparison Edition

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.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 box-and-pointer 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
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, 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}$)`

is equivalent to

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 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]]]]`:

Original	JavaScript
`(define one-through-four (list 1 2 3 4))`	`const one_through_four = list(1, 2, 3, 4);`

Original	JavaScript
`one-through-four(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 one-through-four)1`	`head(one_through_four);1`

Original	JavaScript
`(cdr one-through-four)(2 3 4)`	`tail(one_through_four);[2, [3, [4, null]]]`

Original	JavaScript
`(car (cdr one-through-four))2`	`head(tail(one_through_four));2`

Original	JavaScript
`(cons 10 one-through-four)(10 1 2 3 4)`	`pair(10, one_through_four);[10, [1, [2, [3, [4, null]]]]]`

Original	JavaScript
`(cons 5 one-through-four)(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]

List operations

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 list-ref 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 list_ref is the following:

For $n=0$, list-ref list_ref should return the car head of the list.
Otherwise, list-ref list_ref should return the $(n-1)$st item of the cdr tail of the list.

Original	JavaScript
`(define (list-ref items n) (if (= n 0) (car items) (list-ref (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)) (list-ref 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`

The length procedure function implements a simple recursive plan. The reduction step is:

The length of any list is 1 plus the length of the cdr tail of the list.

This is applied successively until we reach the base case:

The length of the empty list is 0.

We could also compute length in an iterative style:

Original	JavaScript
`(define (length items) (define (length-iter a count) (if (null? a) count (length-iter (cdr a) (+ 1 count)))) (length-iter 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)`

Append 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 cdr tail of list1 and list2, and cons adjoin the car head of list1 onto the result: to the result:

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)); }`

Exercise 2.17 Define a procedure function last-pair last_pair that returns the list that contains only the last element of a given (nonempty) list:

Original	JavaScript
`(last-pair (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)); }`

Exercise 2.18 Define a procedure function reverse that takes a list as argument and returns a list of the same elements in reverse order:

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)`

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); }

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 procedure function first-denomination first_denomination and partly into the procedure function count-change 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 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 us-coins (list 50 25 10 5 1)) (define uk-coins (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);`

We could then call cc as follows:

Original	JavaScript
`(cc 100 us-coins)292`	`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:

Original	JavaScript
`(define (cc amount coin-values) (cond ((= amount 0) 1) ((or (< amount 0) (no-more? coin-values)) 0) (else (+ (cc amount (except-first-denomination coin-values)) (cc (- amount (first-denomination coin-values)) coin-values)))))`	`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 procedures functions first-denomination, first_denomination, except-first-denomination, except_first_denomination, and no-more? no_more in terms of primitive operations on list structures. Does the order of the list coin-values coin_values affect the answer produced by cc? Why or why not?

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); }`

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.

Original		JavaScript
Exercise 2.20 The procedures `+`, ``, and `list` take arbitrary numbers of arguments. One way to define such procedures is to use `define` with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter's value will be a list* of any remaining arguments. For instance, given the definition `(define (f x y . z) $\langle \textit{body} \rangle$)` the procedure `f` can be called with two or more arguments. If we evaluate `(f 1 2 3 4 5 6)` then in the body of `f`, `x` will be 1, `y` will be 2, and `z` will be the list `(3 4 5 6)`. Given the definition `(define (g . w) $\langle \textit{body} \rangle$)` the procedure `g` can be called with zero or more arguments. If we evaluate `(g 1 2 3 4 5 6)` then in the body of `g`, `w` will be the list `(1 2 3 4 5 6)`.[6] Use this notation to write a procedure `same-parity` that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example, `;; same-parity to be given by student` `(same-parity 1 2 3 4 5 6 7)(1 3 5 7)` `(same-parity 2 3 4 5 6 7)(2 4 6)` 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.		Exercise 2.21 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))));`

Mapping over lists

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 (scale-list items factor) (if (null? items) nil (cons (* (car items) factor) (scale-list (cdr items) factor))))`	`function scale_list(items, factor) { return is_null(items) ? null : pair(head(items) * factor, scale_list(tail(items), factor)); }`

Original	JavaScript
`(scale-list (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 higher-order procedure, function, just as in section 1.3. The higher-order 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]]]]`

Now we can give a new definition of scale-list scale_list in terms of map:

Original	JavaScript
`(define (scale-list 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 scale-list, scale_list, the recursive structure of the program draws attention to the element-by-element processing of the list. Defining scale-list 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 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.22 The procedure function square-list square_list takes a list of numbers as argument and returns a list of the squares of those numbers.

Original	JavaScript
`;; square-list to be given by student (square-list (list 1 2 3 4))(1 4 9 16)`	`square_list(list(1, 2, 3, 4));[1, [4, [9, [16, null]]]]`

Here are two different definitions of square-list. square_list. Complete both of them by filling in the missing expressions:

Original	JavaScript
`(define (square-list items) (if (null? items) nil (cons ?? ??)))`	`function square_list(items) { return is_null(items) ? null : pair($\langle{}$??$\rangle$, $\langle{}$??$\rangle$); }`

Original	JavaScript
`(define (square-list items) (map ?? ??))`	`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); }

Exercise 2.23 Louis Reasoner tries to rewrite the first square-list square_list procedure function of exercise 2.22 so that it evolves an iterative process:

Original	JavaScript
`(define (square-list 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); }`

Unfortunately, defining square-list 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 cons: pair:

Original	JavaScript
`(define (square-list 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); }`

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 cons. 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.

Exercise 2.24 The procedure function for-each for_each is similar to map. It takes as arguments a procedure function and a list of elements. However, rather than forming a list of the results, for-each for_each just applies the procedure function to each of the elements in turn, from left to right. The values returned by applying the procedure function to the elements are not used at all—for-each at all—for_each is used with procedures functions that perform an action, such as printing. For example,

Original	JavaScript
`(for-each (lambda (x) (newline) (display x)) (list 57 321 88))57 321 88`	`for_each(x => display(x), list(57, 321, 88));57 321 88`

The value returned by the call to for-each for_each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each. for_each.

Original	JavaScript
	`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] 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 null is used in JavaScript for various purposes, but in this book we shall only use it to represent the empty list.

[5] 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.

[6] To define f and g using lambda we would write (define f (lambda (x y . z) body)) (define g (lambda w body))

[7] 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))

< Previous

Next >

2.2.1 Representing Sequences