# set-1

## Exercise 2.39

Complete the following definitions of `reverse`

(exercise 2.18) in terms of `fold-right`

and `fold-left`

from exercise 2.38:

```
(define (reverse sequence)
(fold-right (lambda (x y) <
````??`>) nil sequence))
(define (reverse sequence)
(fold-left (lambda (x y) <`??`>) nil sequence))

## Exercise 2.38

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 1 2 3))
(fold-left / 1 (list 1 2 3))
(fold-right list nil (list 1 2 3))
(fold-left list nil (list 1 2 3))
```

Give a property that `op`

should satisfy to guarantee that `fold-right`

and `fold-left`

will produce the same values for any sequence.

## Exercise 2.37

Suppose we represent vectors `v` = (`v`_{i}) as sequences of numbers, and matrices `m` = (`m`_{ij}) as sequences of vectors (the rows of the matrix).
For example, the matrix

is represented as the sequence `((1 2 3 4) (4 5 6 6) (6 7 8 9))`

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

We can define the dot product as[17]

```
(define (dot-product v w)
(accumulate + 0 (map * v w)))
```

Fill in the missing expressions in the following procedures for
computing the other matrix operations. (The procedure `accumulate-n`

is defined in exercise 2.36.)

```
(define (matrix-*-vector m v)
(map <
````??`> m))
(define (transpose mat)
(accumulate-n <`??`> <`??`> mat))
(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map <`??`> m)))

## Exercise 2.36

The procedure `accumulate-n`

is similar to `accumulate`

except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the
designated accumulation procedure to combine all the first elements of
the sequences, all the second elements of the sequences, and so on, and
returns a sequence of the results. For instance, if `s`

is a sequence
containing four sequences, `((1 2 3) (4 5 6) (7 8 9) (10 11 12)),`

then the value of `(accumulate-n + 0 s)`

should be the sequence `(22 26 30)`

. Fill in the missing expressions
in the following definition of `accumulate-n`

:

```
(define (accumulate-n op init seqs)
(if (null? (car seqs))
nil
(cons (accumulate op init <
````??`>)
(accumulate-n op init <`??`>))))

## Exercise 2.35

Redefine `count-leaves`

from section 2.2.2 as an accumulation:

```
(define (count-leaves t)
(accumulate <
````??`> <`??`> (map <`??`> <`??`>)))

## Exercise 2.34

Evaluating a polynomial in `x` at a given value of `x` can be
formulated as an accumulation. We evaluate the polynomial

using a well-known algorithm called Horner’s rule, which structures the computation as

In other words, we start with `a`_{n}, multiply by `x`, add `a`_{n-1},
multiply by `x`, and so on, until we reach `a`_{0}.[16] Fill in the following template to produce a procedure that evaluates a polynomial using Horner’s rule. Assume that the coefficients of the polynomial are arranged in a sequence, from `a`_{0} through `a`_{n}.

```
(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms) <??>)
0
coefficient-sequence))
```

For example, to compute 1 + 3`x` + 5`x`^{3} + `x`^{5} at `x` = 2 you would evaluate

`(horner-eval 2 (list 1 3 0 5 0 1))`

`a`

_{n}

`x`

^{n}, then adding

`a`

_{n-1}

`x`

^{n-1}, and so on. In fact, it is possible to prove that any algorithm for evaluating arbitrary polynomials must use at least as many additions and multiplications as does Horner’s rule, and thus Horner’s rule is an optimal algorithm for polynomial evaluation. This was proved (for the number of additions) by A. M. Ostrowski in a 1954 paper that essentially founded the modern study of optimal algorithms. The analogous statement for multiplications was proved by V. Y. Pan in 1966. The book by Borodin and Munro (1975) provides an overview of these and other results about optimal algorithms. [back]

## Exercise 2.33

Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

```
(define (map p sequence)
(accumulate (lambda (x y) <
````??`>) nil sequence))
(define (append seq1 seq2)
(accumulate cons <`??`> <`??`>))
(define (length sequence)
(accumulate <`??`> 0 sequence))

## Exercise 2.29

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

- 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. - Using your selectors, define a procedure
`total-weight`

that returns the total weight of a mobile. - 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.
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?

## Exercise 2.28

Write a procedure `fringe`

that takes as argument a tree
(represented as a list) and returns a list whose elements are all the
leaves of the tree arranged in left-to-right order. For example,

`(define x (list (list 1 2) (list 3 4)))`

`(fringe x)`

(1 2 3 4)`(fringe (list x x))`

(1 2 3 4 1 2 3 4)

## Exercise 2.27

Modify your `reverse`

procedure of exercise 2.18 to
produce a `deep-reverse`

procedure that takes a list as argument and returns as its value the list with its elements reversed and with
all sublists deep-reversed as well. For example,

`(define x (list (list 1 2) (list 3 4)))`

`x`

((1 2) (3 4))`(reverse x)`

((3 4) (1 2))`(deep-reverse x)`

((4 3) (2 1))