Chapter 2

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

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. a. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list ( \(\left.\begin{array}{llllll}1 & 3 & 5 & 7 & 9 & 11\end{array}\right)\). b. What is the order of growth in the number of steps required by list->tree to convert a list of \(n\) elements?

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 Huff man 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.)

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

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?

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- styledescribe 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?

The internal procedures in the scheme-number package are essentially nothing more than calls to the primitive procedures \(+,-\), etc. It was not possible to use the primitives of the language directly because our type-tag system requires that each data object have a type attached to it. In fact, however, all Lisp implementations do have a type system, which they use internally. Primitive predicates such as symbol? and number? determine whether data objects have particular types. Modify the definitions of type-tag, contents, and attach-tag from section 2.4.2 so that our generic system takes advantage of Scheme's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme numbers rather than as pairs whose car is the symbol scheme-number.

Louis Reasoner has noticed that apply-generic may try to coerce the arguments to each other's type even if they already have the same type. Therefore, he reasons, we need to put procedures in the coercion table to "coerce" arguments of each type to their own type. For example, in addition to the scheme- number->complex coercion shown above, he would do: (define (scheme-number->scheme-number n) n) (define (complex->complex z) z) (put-coercion'scheme-number 'scheme-number scheme-number->scheme-number) (put-coercion 'complex 'complex complex->complex) a. With Louis's coercion procedures installed, what happens if apply-generic is called with two arguments of type scheme-number or two arguments of type complex for an operation that is not found in the table for those types? For example, assume that we've defined a generic exponentiation operation: (define (exp x y) (apply-generic' \(\exp x y\) )) and have put a procedure for exponentiation in the Scheme-number package but not in any other package: "following added to Scheme-number package (put'exp' '(scheme-number scheme-number) (lambda (x y) (tag (expt \(x y)\) ))) ;using primitive expt What happens if we call exp with two complex numbers as arguments? b. Is Louis correct that something had to be done about coercion with arguments of the same type, or does apply-generic work correctly as is? c. Modify apply-generic so that it doesn't try coercion if the two arguments have the same type.

Suppose we want to handle complex numbers whose real parts, imaginary parts, magnitudes, and angles can be either ordinary numbers, rational numbers, or other numbers we might wish to add to the system. Describe and implement the changes to the system needed to accommodate this. You will have to define operations such as sine and cosine that are generic over ordinary numbers and rational numbers.

Extend the polynomial system to include subtraction of polynomials. (Hint: You may find it helpful to define a generic negation operation.)