SICP Section 2.3 Symbolic Data

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

1. (list 'a 'b 'c)  
2.   
3. (list (list 'george))  
4. (cdr '((x1 x2) (y1 y2)))  
5.   
6. (cadr '((x1 x2) (y1 y2)))  
7. (pair? (car '(a short list)))  
8. (memq 'red '((red shoes) (blue socks)))  
9.   
10. (memq 'red '(red shoes blue socks))  

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

view plainprint?

1. (list 'a 'b 'c)  
2. (a b c)  
3.   
4. (list (list 'george))  
5. ((george))  
6.   
7. (cdr '((x1 x2) (y1 y2)))  
8. ((y1 y2))  
9.   
10. (cadr '((x1 x2) (y1 y2)))  
11. (y1 y2)  
12.   
13. (pair? (car '(a short list)))  
14. #f  
15.   
16. ;; Memq tries to match individual elements of the outer list.  
17. ;; Since no element of the outer list matches 'red, it returns false.  
18. (memq 'red '((red shoes) (blue socks)))  
19. #f  
20.   
21. (memq 'red '(red shoes blue socks))  
22. (red shoes blue socks)  

(list 'a 'b 'c) (a b c) (list (list 'george)) ((george)) (cdr '((x1 x2) (y1 y2))) ((y1 y2)) (cadr '((x1 x2) (y1 y2))) (y1 y2) (pair? (car '(a short list))) #f ;; Memq tries to match individual elements of the outer list. ;; Since no element of the outer list matches 'red, it returns false. (memq 'red '((red shoes) (blue socks))) #f (memq 'red '(red shoes blue socks)) (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,

1. (equal? '(this is a list) '(this is a list))  

(equal? '(this is a list) '(this is a list))
is true, but

1. (equal? '(this is a list) '(this (is a) list))  

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

Answer:

view plainprint?

1. (define (equal? a b)  
2.   (if (and (pair? a) (pair? b))  
3.       (if (not (equal? (car a) (car b)))  
4.           false  
5.           (equal? (cdr a) (cdr b)))  
6.       (eq? a b)))  

(define (equal? a b) (if (and (pair? a) (pair? b)) (if (not (equal? (car a) (car b))) false (equal? (cdr a) (cdr b))) (eq? a b)))
Exercise 2.55. Eva Lu Ator types to the interpreter the expression

1. (car ''abracadabra)  

(car ''abracadabra)
To her surprise, the interpreter prints back quote. Explain.

Answer: It is easier to understand what happens if we replace the inner ' character with the quote operation. The expression now becomes:

1. (car '(quote abracadabra))  

(car '(quote abracadabra))
This is possible since the ' character is just an easy abbreviation for quote. As the first entity in the list is quote, car returns quote.

Exercise 2.56. Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule



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.

Answer:

view plainprint?

1. (define (make-exponentiation base exponent)  
2.   (cond ((=number? exponent 0) 1)  
3.         ((=number? exponent 1) base)  
4.         (else (list '^ base exponent))))  
5.   
6. (define (exponentiation? x)  
7.   (and (pair? x) (eq? (car x) '^)))  
8.   
9. (define (base e)  
10.   (cadr e))  
11.   
12. (define (exponent e)  
13.   (caddr e))  
14.   
15. (define (deriv exp var)  
16.   (cond ((number? exp) 0)  
17.         ((variable? exp)  
18.          (if (same-variable? exp var) 1 0))  
19.         ((sum? exp)  
20.          (make-sum (deriv (addend exp) var)  
21.                    (deriv (augend exp) var)))  
22.         ((product? exp)  
23.          (make-sum  
24.           (make-product (multiplier exp)  
25.                         (deriv (multiplicand exp) var))  
26.           (make-product (deriv (multiplier exp) var)  
27.                         (multiplicand exp))))  
28.         ((exponentiation? exp)  
29.          (let ((n (exponent exp))  
30.                (u (base exp)))  
31.            (make-product  
32.             (make-product n (make-exponentiation u (- n 1)))  
33.             (deriv u var))))  
34.         (else  
35.          (display "Unknown expression type: ")  
36.          (display exp))))  

(define (make-exponentiation base exponent) (cond ((=number? exponent 0) 1) ((=number? exponent 1) base) (else (list '^ base exponent)))) (define (exponentiation? x) (and (pair? x) (eq? (car x) '^))) (define (base e) (cadr e)) (define (exponent e) (caddr e)) (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) (let ((n (exponent exp)) (u (base exp))) (make-product (make-product n (make-exponentiation u (- n 1))) (deriv u var)))) (else (display "Unknown expression type: ") (display 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

1. (deriv '(* x y (+ x 3)) 'x)  

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

Answer:

view plainprint?

1. (define (augend s)   
2.     (let ((t (cddr s)))  
3.     (if (pair? (cdr t))   
4.         (cons '+ t)   
5.         (car t))))  
6.   
7. (define (multiplicand p)  
8.     (let ((t (cddr p)))  
9.     (if (pair? (cdr t))   
10.         (cons '* t)   
11.         (car t))))  

(define (augend s) (let ((t (cddr s))) (if (pair? (cdr t)) (cons '+ t) (car t)))) (define (multiplicand p) (let ((t (cddr p))) (if (pair? (cdr t)) (cons '* t) (car t))))
Exercise 2.59. Implement the union-set operation for the unordered-list representation of sets.

Answer:

view plainprint?

1. (define (element-of-set? x set)  
2.   (cond ((null? set) false)  
3.         ((equal? x (car set)) true)  
4.         (else (element-of-set? x (cdr set)))))  
5.   
6. (define (adjoin-set x set)  
7.   (if (element-of-set? x set)  
8.       set  
9.       (cons x set)))  
10.           
11. (define (union-set s1 s2)  
12.   (cond ((and (null? s1) (null? s2)) '())  
13.         ((null? s1) s2)  
14.         ((null? s2) s1)  
15.         ((element-of-set? (car s1) s2)  
16.          (union-set (cdr s1) s2))  
17.         (else  
18.          (union-set (cdr s1) (adjoin-set (car s1) s2)))))  

(define (element-of-set? x set) (cond ((null? set) false) ((equal? x (car set)) true) (else (element-of-set? x (cdr set))))) (define (adjoin-set x set) (if (element-of-set? x set) set (cons x set))) (define (union-set s1 s2) (cond ((and (null? s1) (null? s2)) '()) ((null? s1) s2) ((null? s2) s1) ((element-of-set? (car s1) s2) (union-set (cdr s1) s2)) (else (union-set (cdr s1) (adjoin-set (car s1) s2)))))
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?

Answer: Element-of-set? is unchanged from above.

Adjoin-set no longer needs to check for element-of-set?. This version of adjoin-set is O(1) (compared to O(n) earlier).

view plainprint?

1. (define (adjoin-set x set) (cons x set))  

(define (adjoin-set x set) (cons x set))
Union-set no longer needs to check for element-of-set?. This version of union-set is O(n) (compared to O(n^2) earlier)

view plainprint?

1. (define (union-set s1 s2)  
2.   (append s1 s2))  

(define (union-set s1 s2) (append s1 s2))
Intersection-set remains unchanged.

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.

Answer:

view plainprint?

1. (define (adjoin-set x set)  
2.   (define (iter known unknown)  
3.     (if (null? unknown)  
4.         (append known (list x))  
5.         (let ((first (car unknown)))  
6.           (cond ((= x first)   
7.                  set)  
8.                 ((< x first)  
9.                  (append known (list x) unknown))  
10.                 ((> x first)  
11.                  (iter (append known (list first)) (cdr unknown)))))))  
12.   (iter '() set))  

(define (adjoin-set x set) (define (iter known unknown) (if (null? unknown) (append known (list x)) (let ((first (car unknown))) (cond ((= x first) set) ((< x first) (append known (list x) unknown)) ((> x first) (iter (append known (list first)) (cdr unknown))))))) (iter '() set))
Exercise 2.63. Each of the following two procedures converts a binary tree to a list.

view plainprint?

1. (define (tree->list-1 tree)  
2.   (if (null? tree)  
3.       '()  
4.       (append (tree->list-1 (left-branch tree))  
5.               (cons (entry tree)  
6.                     (tree->list-1 (right-branch tree))))))  
7. (define (tree->list-2 tree)  
8.   (define (copy-to-list tree result-list)  
9.     (if (null? tree)  
10.         result-list  
11.         (copy-to-list (left-branch tree)  
12.                       (cons (entry tree)  
13.                             (copy-to-list (right-branch tree)  
14.                                           result-list)))))  
15.   (copy-to-list tree '()))  

(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 '()))
a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?

b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

Answer: a. Both procedures produce same results for all trees.

b. Both procedures have identical orders of growth. Both procedures solve the problem in O(n) steps.

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

Answer:

view plainprint?

1. (define (union-set-tree set1 set2)  
2.   (let ((list1 (list->tree-1 set1))  
3.         (list2 (list->tree-1 set2)))  
4.     (let ((union-list (union-set list1 list2)))  
5.       (list->tree union-list))))  
6.   
7. (define (intersection-set-tree set1 set2)  
8.   (let ((list1 (list->tree-1 set1))  
9.         (list2 (list->tree-1 set2)))  
10.     (let ((intersection-list (intersection-set list1 list2)))  
11.       (list->tree intersection-list))))  

(define (union-set-tree set1 set2) (let ((list1 (list->tree-1 set1)) (list2 (list->tree-1 set2))) (let ((union-list (union-set list1 list2))) (list->tree union-list)))) (define (intersection-set-tree set1 set2) (let ((list1 (list->tree-1 set1)) (list2 (list->tree-1 set2))) (let ((intersection-list (intersection-set list1 list2))) (list->tree intersection-list))))
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.

Answer:

view plainprint?

1. (define (lookup key tree-set-of-records)  
2.   (if (null? tree-set-of-records)   
3.       nil  
4.       (let ((root (entry  tree-set-of-records))  
5.             (left (left-branch tree-set-of-records))  
6.             (right (right-branch tree-set-of-records)))  
7.         (cond ((= key root) root)  
8.               ((< key root)   
9.                (lookup key left))  
10.               ((> key root)   
11.                (lookup key right))))))  

(define (lookup key tree-set-of-records) (if (null? tree-set-of-records) nil (let ((root (entry tree-set-of-records)) (left (left-branch tree-set-of-records)) (right (right-branch tree-set-of-records))) (cond ((= key root) root) ((< key root) (lookup key left)) ((> key root) (lookup key right))))))
Exercise 2.67. Define an encoding tree and a sample message:

view plainprint?

1. (define sample-tree  
2.   (make-code-tree (make-leaf 'A 4)  
3.                   (make-code-tree  
4.                    (make-leaf 'B 2)  
5.                    (make-code-tree (make-leaf 'D 1)  
6.                                    (make-leaf 'C 1)))))  
7.   
8. (define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))  

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

Answer:

1. (decode sample-message sample-tree)  
2. (A D A B B C A)  

(decode sample-message sample-tree) (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.

view plainprint?

1. (define (encode message tree)  
2.   (if (null? message)  
3.       '()  
4.       (append (encode-symbol (car message) tree)  
5.               (encode (cdr message) tree))))  

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

Answer:

view plainprint?

1. (define (encode-symbol symbol tree)  
2.   (define (iter object result)  
3.     (if (leaf? object)  
4.         result  
5.         (let ((lb (left-branch object))  
6.               (rb (right-branch object)))  
7.           (if (contains-symbol? symbol lb)  
8.               (iter lb (append result (list 0)))  
9.               (iter rb (append result (list 1)))))))  
10.   (if (contains-symbol? symbol tree)  
11.       (iter tree '())  
12.       (error "Tree does not contain symbol" tree)))  
13.                     
14. (define (contains-symbol? symbol tree)  
15.   (element-of-set? symbol (symbols tree)))  

(define (encode-symbol symbol tree) (define (iter object result) (if (leaf? object) result (let ((lb (left-branch object)) (rb (right-branch object))) (if (contains-symbol? symbol lb) (iter lb (append result (list 0))) (iter rb (append result (list 1))))))) (if (contains-symbol? symbol tree) (iter tree '()) (error "Tree does not contain symbol" tree))) (define (contains-symbol? symbol tree) (element-of-set? symbol (symbols 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.

view plainprint?

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

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

Answer:

view plainprint?

1. (define (adjoin-set x set)  
2.   (cond ((null? set) (list x))  
3.         ((< (weight x) (weight (car set))) (cons x set))  
4.         (else (cons (car set)  
5.                     (adjoin-set x (cdr set))))))  
6.   
7. (define (successive-merge leaf-set)  
8.   (if (null? (cdr leaf-set))  
9.       (car leaf-set)  
10.       (successive-merge  
11.        (adjoin-set (make-code-tree (car leaf-set)   
12.                                    (cadr leaf-set))   
13.                    (cddr leaf-set)))))  

(define (adjoin-set x set) (cond ((null? set) (list x)) ((< (weight x) (weight (car set))) (cons x set)) (else (cons (car set) (adjoin-set x (cdr set)))))) (define (successive-merge leaf-set) (if (null? (cdr leaf-set)) (car leaf-set) (successive-merge (adjoin-set (make-code-tree (car leaf-set) (cadr leaf-set)) (cddr leaf-set)))))
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?

Answer:

view plainprint?

1. (define rock-alphabet-pairs  
2.   '((a 2)   
3.     (boom 1)   
4.     (get 2)   
5.     (job 2)  
6.     (na 16)   
7.     (sha 3)   
8.     (yip 9)   
9.     (wah 1)))  
10.     
11. (define rock-message  
12.   '(get a job   
13.         sha na na na na na na na na  
14.         get a job   
15.         sha na na na na na na na na  
16.         wah yip yip yip yip yip yip yip yip yip  
17.         sha boom))  
18.   
19. (encode rock-message (generate-huffman-tree rock-alphabet-pairs))  
20. (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)  

(define rock-alphabet-pairs '((a 2) (boom 1) (get 2) (job 2) (na 16) (sha 3) (yip 9) (wah 1))) (define rock-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)) (encode rock-message (generate-huffman-tree rock-alphabet-pairs)) (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)
As there are 8 different symbols we will need log2(8) = 3 bits per alphabet for encoding. There are 36 different alphabets in the message which require 36 * 3 = 108 bits for encoding.