# Revision of *2.2.3 Sequences as Conventional Interfaces* from *30 June 2009 - 8:33pm*

The revisions let you track differences between multiple versions of a post.

Exercises

## 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.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.35

Redefine `count-leaves`

from section 2.2.2 as an accumulation:

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

## 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.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.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.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.40

Define a procedure `unique-pairs`

that, given an integer `n`, generates the sequence of pairs (`i`,`j`) with 1 ≤ `j` < `i` ≤ `n`. Use `unique-pairs`

to simplify the definition of `prime-sum-pairs`

given above.

## Exercise 2.41

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

## Exercise 2.42

The “eight-queens puzzle” asks how to place eight queens on a
chessboard so that no queen is in check from any other (i.e., no two
queens are in the same row, column, or diagonal). One possible
solution is shown in figure 2.8. One way to solve the
puzzle is to work across the board, placing a queen in each column.
Once we have placed `k` - 1 queens, we must place the `k`th queen in a position where it does not check any of the queens already on the
board. We can formulate this approach recursively: Assume that we
have already generated the sequence of all possible ways to place
`k` - 1 queens in the first `k` - 1 columns of the board. For each of
these ways, generate an extended set of positions by placing a queen
in each row of the `k`th column. Now filter these, keeping only
the positions for which the queen in the `k`th column is safe with
respect to the other queens. This produces the sequence of all ways
to place `k` queens in the first `k` columns. By continuing this
process, we will produce not only one solution, but all solutions to
the puzzle.

We implement this solution as a procedure `queens`

, which returns
a sequence of all solutions to the problem of placing `n` queens on an
`n`× `n` chessboard. `Queens`

has an internal procedure `queen-cols`

that returns the sequence of all ways to place queens in the first `k` columns of the board.

```
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
```

In this procedure `rest-of-queens`

is a way to place `k` - 1 queens in the first `k` - 1 columns, and `new-row`

is a proposed row in which to place the queen for the `k`th column. Complete the program by implementing the representation for sets of board positions, including the procedure `adjoin-position`

, which adjoins a new row-column position to a set of positions, and `empty-board`

, which represents an empty set of positions. You must also write the procedure `safe?`

, which determines for a set of positions, whether the queen in the `k`th column is safe with respect to the others. (Note that we need only check whether the new queen is
safe — the other queens are already guaranteed safe with respect to
each other.)

## Exercise 2.43

Louis Reasoner is having a terrible time doing exercise 2.42. His `queens`

procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6 × 6 case.) When Louis asks Eva Lu Ator for help, she points
out that he has interchanged the order of the nested mappings in the `flatmap`

, writing it as

```
(flatmap
(lambda (new-row)
(map (lambda (rest-of-queens)
(adjoin-position new-row k rest-of-queens))
(queen-cols (- k 1))))
(enumerate-interval 1 board-size))
```

Explain why this interchange makes the program run slowly. Estimate
how long it will take Louis’s program to solve the eight-queens
puzzle, assuming that the program in exercise 2.42 solves the puzzle in time `T`.

## Comments

## burberry outlet online

click burberry boots cCkIcXwg [URL=http://www.burberryoutlet-online2013.org/ - burberry sunglasses[/URL - and check coupon code available TGQVTJHn http://www.burberryoutlet-online2013.org/

## a lot of of those charms are shamrocks

Your shamrock is a style that is certainly located on lots of pieces of lolita dress in white and black Celtic jewellery. The one thing persons use rings intended for is just as instant, and a lot of of those charms are shamrocks.

## beats by dre clearance

cheap monster beatsBefore I tell you about my experience,cheap monster beatslet me tell you a bit more about these headphones.beats by dre soloAccording to the information I’ve read, Dr.beats by dre soloDre worked with Monster Cable and Robert Brunner,dre beatsan industrial designer,dre beatsfor more than two years to perfect these headphones.beats by dre clearanceIn Dr. Dre’s words,People aren’t hearing all the musicbeats by dre clearance.## Post new comment