Chapter 2

\begin{aligned} &\text { The procedures }+, * \text {, and list take arbitrary numbers of arguments. One way to } \\ &\text { define such procedures is to use define with dotted-tail notation. In a procedure } \\ &\text { definition, a parameter list that has a dot before the last parameter name indicates } \\ &\text { that, when the procedure is called, the initial parameters (if any) will have as } \\ &\text { values the initial arguments, as usual, but the final parameter's value will be a } \\ &\text { list of any remaining arguments. For instance, given the definition } \\\ &\text { (define (f } \mathrm{x} \mathrm{y} \cdot \mathrm{z} \text { ) }\langle\text { body }\rangle \text { ) } \\ &\text { the procedure } \mathrm{f} \text { can be called with two or more arguments. If we evaluate } \\ &\text { (f } 123456 \text { ) } \\ &\text { then in the body of } \mathrm{f}, \mathrm{x} \text { will be } 1, \mathrm{y} \text { will be } 2, \text { and } \mathrm{z} \text { will be the list }(3456) \text {. } \\ &\text { Given the definition } \\ &\text { (def ine (g. w) }\langle\text { body }\rangle \text { ) } \\ &\text { the procedure g can be called with zero or more arguments. If we evaluate } \\ &\text { (g } 123456 \text { ) } \\ &\text { then in the body of g, w will be the list ( } 1234566 \text { ). } \\\ &\text { Use this notation to write a procedure same-parity that takes one or more } \\ &\text { integers and returns a list of all the arguments that have the same even-odd parity } \\ &\text { as the first argument. For example, } \\ &\text { (same-parity } 1234567 \text { ) } \\ &(1357) \\ &\text { (same-parity } 234567 \text { ) } \\ &(246) \end{aligned}

Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in figure 2.6).

Give combinations of cars and cdrs that will pick 7 from each of the following lists: \(\left(\begin{array}{lllll}1 & 3 & (5 & 7) & 9\end{array}\right)\) ((7)) \((1(2(3(4(5(67))))))\)

A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list): (define (make-mobile left right) (list left right)) A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile: (define (make-branch length structure) (list length structure)) a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch. b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile. c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced. d. Suppose we change the representation of mobiles so that the constructors are (define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure)) How much do you need to change your programs to convert to the new representation?

Define a procedure square-tree analogous to the square-list procedure of exercise \(2.21\). That is, square-tree should behave as follows: Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 23 ), then the set of all subsets is (() (3) (2) (2 3) (1) (\begin{array}{ll 3) (1 2) (1 } 2 3 ) \text { ). } Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works: (define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map (??) rest)))))

Suppose we represent vectors \(v=\left(v_{i}\right)\) as sequences of numbers, and matrices \(m=\left(m_{i j}\right)\) as sequences of vectors (the rows of the matrix). For example, the matrix $$ \left[\begin{array}{llll} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 6 \\ 6 & 7 & 8 & 9 \end{array}\right] $$ is represented as the sequence \(\left(\begin{array}{lllllllllll}1 & 2 & 3 & 4\end{array}\right)\left(\begin{array}{lllllll}4 & 5 & 6 & 6\end{array}\right)\left(\begin{array}{llll}6 & 7 & 8 & 9\end{array}\right)\). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following: $$ \begin{array}{ll} \text { (dot-product } v w \text { ) } & \text { returns the sum } \sum_{i} v_{i} w_{i} ; \\ \text { (matrix-*-vector } m \text { v) } & \text { returns the vector } t, \text { where } t_{i}=\sum_{j} m_{i j} v_{j} ; \\ \text { (matrix-*-matrix } m \text { n ) } & \text { returns the matrix } p, \text { where } p_{i j}=\sum_{k} m_{i k} n_{k j} ; \\ \text { (transpose } m \text { ) } & \text { returns the matrix } n, \text { where } n_{i j}=m_{j i} . \end{array} $$

The accumulate procedure is also known as fold-right, because it combines the first element of the sequence with the result of combining all the elements to the right. There is also a fold-left, which is similar to fold-right, except that it combines elements working in the opposite direction: (define (fold-left op initial sequence) (define (iter result rest) (if (null? rest) result (iter (op result (car rest)) (cdr rest)))) (iter initial sequence)) What are the values of (fold-right / 1 (list 123 )) (fold-left / 1 (list 123 )) (fold-right list nil (list 123 )) (fold-left list nil (list 123 )) Give a property that op should satisfy to guarantee that fold-right and foldleft will produce the same values for any sequence.

Define a procedure unique-pairs that, given an integer \(n\), generates the sequence of pairs \((i, j)\) with \(1 \leq j

Write a procedure to find all ordered triples of distinct positive integers \(i, j\), and \(k\) less than or equal to a given integer \(n\) that sum to a given integer \(s\).