SICP Exercises

Chapter 02 - Part.II

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 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\times 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.) 

; an empty map has no queens
(define empty-board ())

; the adjoint-position returns an list of k possible columns, having the k-th quene
; in the different possition
(define (adjoin-position n k cols)
    (append cols (list n)))

; is the board safe?
; since we already assume that the (k - 1) board is safe,
; we only need to test the last queen on the board
(define (safe? k cols)
    (define (all l) (accumulate (lambda (a b) (and a b)) #t l))
    (define (any l) (accumulate (lambda (a b) (or  a b)) #f l))
    (define (diag? col la)
        (define (iter i c ret)
            (if (null? c) ret
                (iter (+ i 1) (cdr c)
                      (cons (= (abs (- k i)) (abs (- la (car c)))) ret))))
    (any (iter 1 col '())))
    (let ((la (last cols))
          (hs (take cols (- (length cols) 1))))
    (not (or (any (map (lambda (a) (= a la)) hs)) (diag? hs la)))))

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\).

First of all, the queen precedure will be running in the procedure safe?, so the less times safe? being invoked, the less time will be used solving the puzzle.

The former flatmap looks like this: 

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

For an 8x8 puzzle, this one will first emurate every 8x1 board with one quenee on it, then append another column, try every possible combinations, filter out unsafe ones, then append a third column... until all 8 quenes are on the board safely. For an 8x8 board, 15720 times safe? will be invoked.

As for Louis's solution, with the two iterative flipped, this precedure solving an 8x8 problem by solving every 7x8, 6x8, ..., 1x8 problem, append another column, filter out "unsafe" ones, and return the result. Apperently, solving 6x8, 5x8, ..., 1x8 problems are not necessary here, and worese, this precedure will try solve each of the 7x8, 6x8, ..., 1x8 problem in a same manner, that is to solving 7x8 problem, it needs to solve 6x8, ..., 1x8 problems, and to solve the 6x8 problem inside the 7x8 problem, it needs to solve 5x8, ..., 1x8 problems... That is why it seems take forever even when \(n\) is not too large.

The original solution is basicaly enumerate every possible position of queens on the board, so it has an complacity of \(O(n^n)\) or \(O(n^{-\frac 12}n!)\). And with the flipped iterative, solving a \(n\times n\) problem will result in solving each smaller board in a full recursive manner, so the time complacity would be \(O(n^{n^n})\).

Here are some test: (measured in times of safe? invoked, this should be the same in different implementations of safe?)

n original flipped ratio (flipped / original)
1 1 1 1.0
2 6 8 1.33
3 60 18 3.33
4 624 60 10.4
5 8160 220 37.09
6 128904 894 144.189

Exercise 2.44

Define the procedure up-split used by corner-split. It is similar to right-split, except that it switches the roles of below and beside. 

(define (up-split painter n)
  (if (= n 0) painter
      (let ((smaller (up-split painter (- n 1))))
      (below painter(beside smaller smaller)))))

Exercise 2.45

right-split and up-split can be expressed as instances of a general splitting operation. Define a procedure split with the property that evaluating 

(define right-split (split beside below))
(define up-split (split below beside))

produces procedures right-split and up-split with the same behaviors as the ones already defined. 

(define (splite c1 c2) (lambda (painter n)
    (if (= n 0) painter
        (let ((smaller ((split c1 c1) painter (- n 1))))
        (c1 painter (c2 smaller smaller))))))

Exercise 2.46

A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate. Implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of your selectors and constructor, implement procedures add-vect, sub-vect, and scale-vect that perform the operations vector addition, vector subtraction, and multiplying a vector by a scalar:

\[ \begin{alignat}{1} \left(x_1,y_1\right) &+& \left(x_2,y_2\right) &=& \left(x_1+x_2,y_1+y_2\right) \cr \left(x_1,y_1\right) &+& \left(x_2,y_2\right) &=& \left(x_1-x_2,y_1-y_2\right) \cr a &\cdot& \left(x,y\right) &=& \left(ax,ay\right) \cr \end{alignat} \] 
(define make-vect cons)
(define xcor-vect car)
(define ycor-vect cdr)
(define (add-vect v1 v2)
    (make-vect (+ (xcor-vect v1) (xcor-vect v2))
               (+ (ycor-vect v1) (ycor-vect v2))))
(define (sub-vect v1 v2)
    (make-vect (- (xcor-vect v1) (xcor-vect v2))
               (- (ycor-vect v1) (ycor-vect v2))))
(define (scale-vect a v)
    (make-vect (* a (xcor-vect v)) (* a (ycor-vect v))))

Exercise 2.47

Here are two possible constructors for frames: 

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

For each constructor supply the appropriate selectors to produce an implementation for frames. 

; first two are the same
(define origin-frame car)
(define edge1-frame cadr)

; edge2 using list
(define edge2-frame caddr)

; edge2 using cons
(define edge2-frame cddr)

Exercise 2.48

A directed line segment in the plane can be represented as a pair of vectors -- the vector running from the origin to the start-point of the segment, and the vector running from the origin to the end-point of the segment. Use your vector representation from exercise 2.46 to define a representation for segments with a constructor make-segment and selectors start-segment and end-segment. 

(define make-segment cons)
(define start-segment car)
(define end-segment cdr)

Exercise 2.49

Use segments->painter to define the following primitive painters:

a. The painter that draws the outline of the designated frame.

b. The painter that draws an ``X'' by connecting opposite corners of the frame.

c. The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.

d. The wave painter. 

; outline
(define outline (lambda (frame)
    (let ((p1 (origin-vect frame))
          (p2 (add-vect (origin-vect frame) (edge1-vect frame)))
          (p3 (add-vect (origin-vect frame) (add-vect (edge1-vect frame) (edge2-vect frame)))
          (p4 (add-vect (origin-vect frame) (edge2-vect frame)))))
    (segments->painter (list (make-segment p1 p2) (make-segment p2 p3)
                             (make-segment p3 p4) (make-segment p4 p1))))))

; X mark
(define X (lambda (frame)
    (let ((p1 (origin-vect frame))
          (p2 (add-vect (origin-vect frame) (edge1-vect frame)))
          (p3 (add-vect (origin-vect frame) (add-vect (edge1-vect frame) (edge2-vect frame)))
          (p4 (add-vect (origin-vect frame) (edge2-vect frame)))))
    (segments->painter (list (make-segment p1 p3) (make-segment p2 p4))))))

; diamond
(define diamond (lambda (frame)
    (define (midpoint p1 p2) (scale-vect 0.5 (add-vect p1 p2)))
    (let ((p1 (origin-vect frame))
          (p2 (add-vect (origin-vect frame) (edge1-vect frame)))
          (p3 (add-vect (origin-vect frame) (add-vect (edge1-vect frame) (edge2-vect frame)))
          (p4 (add-vect (origin-vect frame) (edge2-vect frame)))))
    (let ((m1 (midpoint p1 p2))
          (m2 (midpoint p2 p3))
          (m3 (midpoint p3 p4))
          (m4 (midpoint p4 p0)))
    (segment->painter (list (make-segment m1 m2) (make-segment m2 m3)
                            (make-segment m3 m4) (make-segment m4 m1)))))))
; nothing new in wave, skip

Exercise 2.50

Define the transformation flip-horiz, which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees. 

(define (flip-horiz painter)
    (transform-painter painter (make-vert 1.0 0.0)
                               (make-vert 0.0 0.0)
                               (make-vert 1.0 1.0)))
(define (rotate-180 painter)
    (transform-painter painter (make-vert 1.0 1.0)
                               (make-vert 0.0 1.0)
                               (make-vert 1.0 0.0)))
(define (rotate-270 painter)
    (transform-painter painter (make-vert 1.0 0.0)
                               (make-vert 1.0 1.0)
                               (make-vert 0.0 0.0)))

Exercise 2.51

Define the below operation for painters. Below takes two painters as arguments. The resulting painter, given a frame, draws with the first painter in the bottom of the frame and with the second painter in the top. Define below in two different ways -- first by writing a procedure that is analogous to the beside procedure given above, and again in terms of beside and suitable rotation operations (from exercise 2.50). 

; in a way analogous to beside
(define (below painter1 painter2)
    (let ((mid-point (make-vert 0.0 0.5)))
    (let ((top-part (transform-painter painter2 mid-point
                                                (make-vert 0.5 1.0)
                                                (make-vert 1.0 1.0)))
          (bot-part (transform-painter painter1 (make-vert 0.0 0.0)
                                                (make-vert 1.0 0.0)
                                                mid-point)))
    (lambda (frame)
    (top-part frame)
    (bot-part frame)))))

; using rotates and beside
(define (below painter1 painter2)
    (rotate-90 (beside (rotate-270 painter2) (rotate-270 painter1))))

Exercise 2.52

Make changes to the square limit of wave shown in figure 2.9 by working at each of the levels described above. In particular:

a. Add some segments to the primitive wave painter of exercise 2.49 (to add a smile, for example).

b. Change the pattern constructed by corner-split (for example, by using only one copy of the up-split and right-split images instead of two).

c. Modify the version of square-limit that uses square-of-four so as to assemble the corners in a different pattern. (For example, you might make the big Mr. Rogers look outward from each corner of the square.)

Boring one, skipped...

Exercise 2.53

What would the interpreter print in response to evaluating each of the following expressions? 

(list 'a 'b 'c)

(list (list 'george))
(cdr '((x1 x2) (y1 y2)))

(cadr '((x1 x2) (y1 y2)))
(pair? (car '(a short list)))
(memq 'red '((red shoes) (blue socks)))

(memq 'red '(red shoes blue socks))

(list 'a 'b 'c)
; returns (a b c)

(list (list 'george))
; returns ((george))
(cdr '((x1 x2) (y1 y2)))
; returns ((y1 y2))

(cadr '((x1 x2) (y1 y2)))
; returns (y1 y2)
(pair? (car '(a short list)))
; returns #f
(memq 'red '((red shoes) (blue socks)))
; returns #f
(memq 'red '(red shoes blue socks))
; returns (red shoes blue socks)

Exercise 2.54

Two lists are said to be equal? if they contain equal elements arranged in the same order. For example, (equal? '(this is a list) '(this is a list)) is true, but (equal? '(this is a list) '(this (is a) list)) is false.

To be more precise, we can define equal? recursively in terms of the basic eq? equality of symbols by saying that a and b are equal? if they are both symbols and the symbols are eq?, or if they are both lists such that (car a) is equal? to (car b) and (cdr a) is equal? to `(cdr b)`. Using this idea, implement equal? as a procedure. 

(define (equal? a b)
    (let ((pa? (pair? a))
          (pb? (pair? b)))
    (cond ((and (null? a) (null? b)) #t)
          ((and (not pa?) (not pb?)) (eq? a b))
          ((or (and pa? (not pb?)) (and pb? (not pa?))) #f)
          (else (and (equal? (car a) (car b)) (equal? (cdr a) (cdr b)))))))

Exercise 2.55

Eva Lu Ator types to the interpreter the expression (car ''abracadabra) To her surprise, the interpreter prints back quote. Explain.

When you type 'abc to the interpreter, the interpreter will return (quote abc), which means that the ' notion is just an syntax sugar for quote. So ''abc' will become '(quote abc), therefore car will return quote.

Exercise 2.56 Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule \(\frac{{\rm d}u^n}{{\rm d}x}=nu^{n-1}\frac{{\rm d}u}{{\rm d}x}\) by adding a new clause to the deriv program and defining appropriate procedures exponentiation?, base, exponent, and make-exponentiation. (You may use the symbol ** to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. 

; implement the new rules
(define (make-exponentiation b e)
    (cond ((number? b) (exp b e))
          ((= e 0) 1)
          ((= e 1) b)
          (else (list '** b e))))
(define base cadr)
(define exponent caddr)
(define (exponentiation? e)
    (and (pair? e) (eq? '** (car e))))

; new deriv
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ((exponentiation? exp)
            (make-product
                (exponent exp)
                (make-product (make-exponentiation (base exp) (- (exponent exp) 1))
                              (deriv (base exp) var))))
        (else
         (error "unknown expression type -- DERIV" exp))))

Exercise 2.57

Extend the differentiation program to handle sums and products of arbitrary numbers of (two or more) terms. Then the last example above could be expressed as (deriv '(* x y (+ x 3)) 'x).

Try to do this by changing only the representation for sums and products, without changing the deriv procedure at all. For example, the addend of a sum would be the first term, and the augend would be the sum of the rest of the terms. 

; sum
(define (make-sum . e)
    (let ((numbers (fold + 0 (filter (lambda (x) (number? x)) e)))
          (vars (filter (lambda (x) (not (number? x))) e)))
    (cond ((= 0 numbers)
        (cond ((null? vars) 0)
              ((null? (cdr vars)) (car vars))
              (else (cons '+ vars))))
          (else (cond ((null? vars) numbers)
                      (else (cons '+ (cons numbers vars))))))))
(define addend cadr)
(define (augend e)
    (let ((aug (cddr e)))
    (if (null? (cdr aug)) (car aug) (cons '+ aug))))

; products
(define (make-prouct . e)
    (let ((numbers (fold * 1 (filter (lambda (x) (number? x)) e)))
          (vars (filter (lambda (x) (not (number? x))) e)))
    (cond ((= 0 numbers) 0)
          ((= 1 numbers) (cond ((null? vars) 1)
                               ((null? (cdr vars)) (car vars))
                               (else (cons '+ vars))))
          (else (cond ((null? vars) numbers)
                      (else (cons '+ (cons numbers vars))))))))
(define multiplier cadr)
(define (multiplicand e)
    (let ((aug (cddr e)))
    (if (null? (cdr aug)) (car aug) (cons '* aug))))

One more thing, without a proper simplifier, the result is pretty messed up, and no sane soul will write some thing like this: 

]=> (deriv '( * x x x x y) 'x)
    (+ (* x (+ (* x (+ (* x y) (* x y))) (* x x y))) (* x x x y))

This is indeed the correct answer, but badly shaped.

Exercise 2.58

Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which + and * are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate.

a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as (x + (3 * (x + (y + 2)))). To simplify the task, assume that + and * always take two arguments and that expressions are fully parenthesized.

b. The problem becomes substantially harder if we allow standard algebraic notation, such as (x + 3 * (x + y + 2)), which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates, selectors, and constructors for this notation such that our derivative program still works?

a. With all proper parentheses in the expersion, it is an simple task. 

(define (make-sum e1 e2)
    (cond ((and (number? e1) (= e1 0)) e2)
          ((and (number? e2) (= e2 0)) e1)
          ((and (number? e1) (number? e2)) (+ e1 e2))
          (else (list e1 '+ e2))))
(define (sum? e) (eq? '+ (cadr e)))
(define addend car)
(define augend caddr)

(define (make-product e1 e2)
    (cond ((or (=number? e1 0) (=number? e2 0)) 0)
          ((and (number? e1) (number? e2)) (* e1 e2))
          ((=number? e1 1) e2)
          ((=number? e2 1) e1)
          (else (list e1 '* e2))))
(define (product? e) (eq? '* (cadr e)))
(define multiplier car)
(define multiplicand caddr)

b. This one can be very complex. But here we only support two operation, + and *, things will become much easier. Only need to change augend and multiplicand in perivious exercise.

The idea is similiar to ex2.57, which is take the expersion as two part, the first term, and the rest of it, without the operator in between. The only different is we need to bundle the chain of * in augend, which basically trun 2 + 3 * 4 * 5 + 6 into 2 + (3 * 4 * 5) + 6, and then, the (3 * 4 * 5) can be processed in trun. This is to avoid the complicity because of precedence and take advantage of the language itself. 

(define (augend e)
    ; the most complex part, need to bundle next chain of * into a list
    ; i.e. trun upcoming 4 * 5 * 6 + 7 to (4 * 5 * 6) + 7
    (define (helper in bundle)
        (let ((e  (car in))
              (es (cdr in)))
        (cond ((null? es) (if (null? bundle) e (append bundle (list '* e))))
              ((eq? (car es) '*)
                (if (null? bundle) (helper (cdr es) (list e))
                    (helper (cdr es) (append bundle (list '* e)))))
              (else
                (if (null? bundle) in
                    (append (list (append bundle (list '* e))) es))))))
    (let ((t (cddr e)))
    (cond ((pair? (car t)) (car t))
          (else (helper t '())))))

; no need to bundle anything here, for * has the highest precedence in this
; exercises
(define (multiplicand e)
    (cond ((pair? (caddr e)) (caddr e))
          (else (cddr e))))

Exercise 2.59

Implement the union-set operation for the unordered-list representation of sets. 

(define (union-set set1 set2)
    (if (null? set2) set1)
        (let ((x  (car set2))
              (xs (cdr set2)))
        (if (element-of-set? x set1)
            (union-set set1 xs)
            (union-set (adjoin-set x set1) xs))))

Exercise 2.60

We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as the list (2 3 2 1 3 2 2). Design procedures element-of-set?, adjoin-set, union-set, and intersection-set that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one?

The precedure element-of-set and intersection-set should remain same, only union-set and adjoin-set need to rewrite. 

(define union-set append)
(define adjoin-set cons)

Since there is no need to eliminate duplicate element, simply join two part of the set will do.

As for efficiency, unoin-set and adjoint-set will significant faster than non-duplicate representation. But while the set grow larger and with a lot of duplicated element, element-of-set? and intersect-set will mush slower.

Exercise 2.61

Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation. 

(define (adjoin-set x set)
    (define (iter xs res)
        (cond ((null? xs) (append res (list x)))
              ((= x (car xs)) set)
              ((< x (car xs)) (append res (cons x xs)))
              ((> x (car xs)) (iter (cdr xs) (append res (list (car xs)))))))
    (iter set '()))

Exercise 2.62

Give a \(O(n)\) implementation of union-set for sets represented as ordered lists. 

(define (union-set set1 set2)
    (define (iter s1 s2 res)
        (cond ((null? s1) (append res s2))
              ((null? s2) (append res s1))
              (else (let ((x1 (car s1)) (x2 (car s2)))
                    (cond ((= x1 x2) (iter (cdr s1) (cdr s2) (append res (list x1))))
                          ((> x1 x2) (iter s1       (cdr s2) (append res (list x2))))
                          ((< x1 x2) (iter (cdr s1) s2       (append res (list x1)))))))))
    (iter set1 set2 '()))

Exercise 2.63

Each of the following two procedures converts a binary tree to a list. 

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

Tree

Since both tree->list-1 and tree->list-2 convert a tree into a list in a "left-subtree, entry, right-subtree" way, which is an "inorder traversal" path to an tree. All 3 trees in the figue returns the list (1 3 5 7 9 11).

The different of times of list operation (Consider cons as 1 operation, append a list at length of m considered m operations) used between the two precedure is huge. tree->list-2 take less operations, for it does not have a lot of append and cons one element to the result on each node traversed. So the tree->list-2 has the order of list operation of \(O(n)\). While tree->list-1 has to append a list of right-subtree to left-subtree. So the order of list operation would be \(O(n^2)\) for the most unbalanced tree, but \(O(n{\rm log}n)\) for a balanced tree.

Exercise 2.64

The following procedure list->tree converts an ordered list to a balanced binary tree. The helper procedure partial-tree takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list. The result returned by partial-tree is a pair (formed with cons) whose car is the constructed tree and whose cdr is the list of elements not included in the tree. 

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

Here is how list->tree works with given list (1 3 5 7 9 11): 

(partial-tree '(1 3 5 7 9 11) 6)
  |==> left tree (partial-tree '(1 3 5 7 9 11) 2)
    |==> left tree (partial-tree '(1 3 5 7 9 11) 1)
      |==> left tree (partial-tree '(1 3 5 7 9 11) 0) <==| returns (cons '() '(1 3 5 7 9 11))
      |==> right tree (partial '(3 5 7 9 11) 0) <==| returns (cons '() '(3 5 7 9 11))
    <==| left tree returns '(1 () ())
    <==| right tree returns '()
  <==| left tree returns '(3 (1 () ()) ())
  |==> right tree (partial-tree '(7 9 11) 3)
    |==> left tree (partial-tree '(7 9 11) 1)
    ...
    <==| left tree returns '(7 () ())
    ...
    <==| right tree returns '(11 () ())
  <== right tree returns '(9 (7 () ()) (11 () ()))
==> got the whole tree: '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ())))'

This is the same tree as the 3rd tree in the figure of last exercises.

Since this precedure calls make-tree and take of an element in the list each time of partial-tree invoked, the order of growth is \(O(n)\) for a list of n elements.

Exercise 2.65

Use the results of exercises 2.63 and 2.64 to give \(O(n)\) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees

Merging two balanced tree into a new balanced tree is never easy. The idea is simplily flatten two tree into sorted list, supporsed the trees is build from from well sorted lists, union/intersect the merged list, then convert it back to a balanced tree. Each step has a order of growth \(O(n)\), so at a whole, it is \(O(n)\). The precedure with -list in suffix refer to those coresponding precedures to deal with set with sorted-list representation. 

(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          (else
            (list->tree (union-set-list (tree->list-2 set1)
                                        (tree->list-2 set2))))))
(define (intersection-set set1 set2)
    (cond ((or (null? set1) (null? set2)) '())
          (else
            (list->tree (intersection-seti-list (tree->list-2 set1)
                                                (tree->list-2 set2))))))

Exercise 2.66

Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys. 

(define (lookup given-key set)
    (if (null? set) '()
        (let ((this-entry (entry set)))
        (let ((this-key (key this-entry)))
        (cond ((= this-key given-key) this-entry)
              ((> this-key given-key) (lookup given-key (left-tree this-entry)))
              ((< this-key given-key) (lookup given-key (right-tree this-entry))))))))

Exercise 2.67

Define an encoding tree and a sample message: 

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))
(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

Use the decode procedure to decode the message, and give the result.

Result is list (a d a b b c a)

Exercise 2.68

The encode procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message. 

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

encode-symbol is a procedure, which you must write, that returns the list of bits that encodes a given symbol according to a given tree. You should design encode-symbol so that it signals an error if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in exercise 2.67 with the sample tree and seeing whether it is the same as the original sample message. 

(define (encode-symbol sym tree)
    (define (iter branch res)
        (cond ((leaf? branch) res)
              ((memq sym (symbols (left-branch branch)))
                (iter (left-branch branch) (cons 0 res)))
              ((memq sym (symbols (right-branch branch)))
                (iter (right-branch branch) (cons 1 res)))))
    (reverse (iter tree '())))

Exercise 2.69

The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm. 

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

make-leaf-set is the procedure given above that transforms the list of pairs into an ordered set of leaves. successive-merge is the procedure you must write, using make-code-tree to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.) 

(define (successive-merge ps)
    (define (repeat time p) (lambda (x)
        (cond ((= time 0) '())
              ((= time 1) x)
              (else ((repeat (- time 1) p) (p x))))))
    (define (merge-1 xs)
        (adjoin-set (make-code-tree (car xs) (cadr xs)) (cddr xs)))
    ((repeat (- (length ps) 1) merge-1) ps))

The inner precedure merge-1 will merge the first two element together, and put it back to a proper position in the list using adjoin-set. Repeat this step n times for a list of n element will get a proper Huffman tree.

This is not as triky as Exercises 2.58. That one is really tricky.

Exercise 2.70

The following eight-symbol alphabet with associated relative frequencies was designed to efficiently encode the lyrics of 1950s rock songs. (Note that the "symbols" of an "alphabet" need not be individual letters.) 

A     2   NA  16
BOOM  1   SHA  3
GET   2   YIP  9
JOB   2   WAH  1

Use generate-huffman-tree (exercise 2.69) to generate a corresponding Huffman tree, and use encode (exercise 2.68) to encode the following message: 

Get a job
Sha na na na na na na na na
Get a job
Sha na na na na na na na na
Wah yip yip yip yip yip yip yip yip yip
Sha boom

How many bits are required for the encoding? What is the smallest number of bits that would be needed to encode this song if we used a fixed-length code for the eight-symbol alphabet?

The Huffman encodings of this song takes 84 bits, the whole messege is 

111111100111101110000000001111111001111011100000000011010101010101010101010111011011

But if we use a fix length encoding, each word needs 3-bit for each can encoding 8 different word. Therefore, 108 bits for the whole messege.

Exercise 2.71

Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., \(2^{n-1}\). Sketch the tree for n=5; for n=10. In such a tree (for general n) how many bits are required to encode the most frequent symbol? the least frequent symbol?

Using symbol a-e to note the 5 symbols, the Huffman tree lookes like this:

n = 5

The tree when n=10 is similiar to n=5, but has more level. In gereral, to encode the most frequent symbol alway takes 1 bit (simplily 0), and n bits for the least frequent symbol (11...1, n times 1).

Exercise 2.72

Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of the n symbols are as described in exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet.

If the distribution of symbols follows ex2.71, i.e. each symbol's occourance is 1, 2, 4, ..., \(2^{n-1}\), encoding the most frequent symbol takes \(O(1)\) step, while \(O(n)\) for the least frequent symbol. If we consider the ocourance of each symbol into account, to encode a message at length of n will takes \(n\sum_{i=1}^n i\times\frac{2^{i-1}}{2^n-1}\) steps in average, which is surprisingly less then \(4n\) for every \(n\ge3\), even irrelvent to the size of alphbet.

Exercise 2.73

Section 2.3.2 described a program that performs symbolic differentiation: 

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ;<more rules can be added here>
        (else (error "unknown expression type -- DERIV" exp))))

We can regard this program as performing a dispatch on the type of the expression to be differentiated. In this situation the "type tag" of the datum is the algebraic operator symbol (such as +) and the operation being performed is deriv. We can transform this program into data-directed style by rewriting the basic derivative procedure as: 

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get 'deriv (operator exp)) (operands exp)
                                            var))))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
  1. Explain what was done above. Why can't we assimilate the predicates number? and same-variable? into the data-directed dispatch?
  2. Write the procedures for derivatives of sums and products, and the auxiliary code required to install them in the table used by the program above.
  3. Choose any additional differentiation rule that you like, such as the one for exponents (exercise 2.56), and install it in this data-directed system.
  4. In this simple algebraic manipulator the type of an expression is the algebraic operator that binds it together. Suppose, however, we indexed the procedures in the opposite way, so that the dispatch line in deriv looked like 
((get (operator exp) 'deriv) (operands exp) var)

What corresponding changes to the derivative system are required?

The reason for number? and same-variable can't assimilated into data-directed dispatch is they are dealing with data without data-tag.

The precedure to derives sum and product looks likes this: 

(define (deriv-add expr) 
    (make-sum (deriv (addend expr))
              (deriv (augend expr))))
(define (deriv-prod expr)
    (let ((exp1 (multiplicand expr))
          (exp2 (multiplication expr)))
    (make-sum (make-product exp1 (deriv exp2))
              (make-product exp2 (deriv exp1)))))
(put 'deriv '(+) deriv-add)
(put 'deriv '(*) deriv-prod)

Add exponent to deriv. Using precedures in previous exercises. 

(define (deriv-exponent expr)
    (make-product
        (exponent expr)
        (make-product (make-exponentiation (base expr) (- (exponent expr) 1))
                      (deriv (base expr) var))))

If we want to use dispatch line like ((get (operator exp) 'deriv) (operands exp) var))), we need to implement operator and operands precedures. 

(define operator car)
(define operands (lambda (x) x))

Exercise 2.74

Insatiable Enterprises, Inc., is a highly decentralized conglomerate company consisting of a large number of independent divisions located all over the world. The company's computer facilities have just been interconnected by means of a clever network-interfacing scheme that makes the entire network appear to any user to be a single computer. Insatiable's president, in her first attempt to exploit the ability of the network to extract administrative information from division files, is dismayed to discover that, although all the division files have been implemented as data structures in Scheme, the particular data structure used varies from division to division. A meeting of division managers is hastily called to search for a strategy to integrate the files that will satisfy headquarters' needs while preserving the existing autonomy of the divisions.

Show how such a strategy can be implemented with data-directed programming. As an example, suppose that each division's personnel records consist of a single file, which contains a set of records keyed on employees' names. The structure of the set varies from division to division. Furthermore, each employee's record is itself a set (structured differently from division to division) that contains information keyed under identifiers such as address and salary. In particular:

a. Implement for headquarters a get-record procedure that retrieves a specified employee's record from a specified personnel file. The procedure should be applicable to any division's file. Explain how the individual divisions' files should be structured. In particular, what type information must be supplied?

b. Implement for headquarters a get-salary procedure that returns the salary information from a given employee's record from any division's personnel file. How should the record be structured in order to make this operation work?

c. Implement for headquarters a find-employee-record procedure. This should search all the divisions' files for the record of a given employee and return the record. Assume that this procedure takes as arguments an employee's name and a list of all the divisions' files.

d. When Insatiable takes over a new company, what changes must be made in order to incorporate the new personnel information into the central system?

Short answer, how the files structured in each division dose not matter much, as long as it suits the needs of each division. The HQ may holds a list of all personnel, detailing which division each personnel belongs, and syncronize it with each division on every personnel changes. When the HQ calls get-record, it looks up in the personnel list, knowing which division to querry, and then send a request to the coresponding division. The division get this request, doing theri local search, and return thr record in a unified format, meaning each division shall implement their own constrotor, but returns a same representation. Then get-salary shall just extract the information from the record as a selector. find-employee-record works like a filter-map, like 

(define (find-employee-record name)
    (map get-record (filter (lambda (x) (eq? name x)) employee-name-list)))

shall do.

Adding a new division is simple in this design. Just implement the constrotor for record locally, and an interface to process requests come from HQ, and return the record. Then syncronize the employee list to HQ.

The most tricky part in this design is how to syncronize the employee list. This is indeed a very complex problem cannot be avoided in a distributed system.

Exercise 2.75

Implement the constructor make-from-mag-ang in message-passing style. This procedure should be analogous to the make-from-real-imag procedure given above. 

(define (make-from-mag-ang r t)
    (define (dispatch op)
        (cond ((eq? op 'real-part) (* r (sin t)))
              ((eq? op 'imag-part) (* r (cos t)))
              ((eq? op 'magnitude) r)
              ((eq? op 'angle)     t))
              (else "Unknown op ---" op))
    dispatch)

Exercise 2.76

As a large system with generic operations evolves, new types of data objects or new operations may be needed. For each of the three strategies -- generic operations with explicit dispatch, data-directed style, and message-passing-style -- describe the changes that must be made to a system in order to add new types or new operations. Which organization would be most appropriate for a system in which new types must often be added? Which would be most appropriate for a system in which new operations must often be added?

Add a new operation to the system when using explicit dispatch need to modified all involved precedure, adding approperated branches. This method need huge amount of work, and will affect exisiting code in an unpredicatable way (introducing new bug, forget some branches, recurssion, etc.). The same thing happens when we add a new type to the system. This really sucks.

In data-directed style program, we will only need insert new implement into global add to the system, which means whatever we want to add to the system, we can simplily append the source to the original source without touching any already exisiting source, which makes it the most simple way to add new feature of old system. But all these come with a price, for in a large system, the dispatch table can be huge. This will resulting in a big overhead when the dispatcher lookup in the table, and find the which precedure to call. Also, dealing the tag in data can also have a tiny overhead. And we still need to worry about name comflict, but dealing with it is much easier in comperison to explicit dispatch style. This is the best way foe system with bunch of "fixed" precedure, but need to add new type often.

Message passing comes in the middle. We need add new branches into all involving precedure when adding new types, lots of work, but less than explicit dispatch. Adding new precedure is much easier, only need to implement them. But we do not have to worry about name comflict at all, for everything is in a closure. And this style does not have the overhead of looking up the dispatch table and deal with the tag in the data. This is the best way for a system needs new operations must often be added, and need convertions between types often.