(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 'red '((red shoes) (blue socks))) -> #f
(memq 'red '(red shoes blue socks)) -> (red shoes blue socks)
(define (equal? a b)
(cond ((and (pair? a) (pair? b))
(and (equal? (car a) (car b))
(equal? (cdr a) (cdr b))))
((not (or (pair? a) (pair? b)))
(eq? a b))
(else #f)))
''abracadabra is an abbreviation of (list 'quote 'abracadabra) ; its first element is 'quote .
(define (exponentiation? e)
(and (pair? e) (eq? (car e) '**)))
(define (base e)
(cadr e))
(define (exponent e)
(caddr e))
(define (make-exponentiation base exponent)
(cond ((=number? exponent 0) 1)
((=number? exponent 1) base)
((and (number? base) (number? exponent))
(expt base exponent))
(else (list '** base exponent))))
(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)
(make-sum (exponent exp) -1))
(deriv (base exp) var))))
(else (error "unknown expression type -- DERIV" exp))))
(define (augend e)
(let ((rem (cddr e)))
(if (null? (cdr rem))
(car rem)
(cons '+ rem))))
(define (multiplicand e)
(let ((rem (cddr e)))
(if (null? (cdr rem))
(car rem)
(cons '* rem))))
a.
(define (sum? e)
(and (pair? e) (eq? (cadr e) '+)))
(define (addend e)
(car e))
(define (augend e)
(caddr e))
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
((equal? a1 a2) (make-product a1 2))
(else (list a1 '+ a2))))
(define (product? e)
(and (pair? e) (eq? (cadr e) '*)))
(define (multiplier e)
(car e))
(define (multiplicand e)
(caddr e))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list m1 '* m2))))
b. A simple solution works under the assumption that the expression contains only additions and multiplications. An expression is a sum if it contains any '+ in its topmost “layer” , otherwise, a product.
(define (sum? e)
(and (pair? e)
(not (null? (cdr e)))
(or (eq? (cadr e) '+)
(sum? (cddr e)))))
(define (addend e)
(if (eq? (cadr e) '+)
(car e)
(cons (car e)
(cons (cadr e)
(let ((rem (addend (cddr e))))
(if (pair? rem)
rem
(list rem)))))))
(define (augend e)
(let ((rem (cddr e)))
(if (eq? (cadr e) '+)
(if (null? (cdr rem)) (car rem) rem)
(augend rem))))
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (append (if (pair? a1) a1 (list a1))
(if (pair? a2) (cons '+ a2) (list '+ a2))))))
(define (product? e)
(not (sum? e)))
(define (multiplier e)
(car e))
(define (multiplicand e)
(let ((rem (cddr e)))
(if (null? (cdr rem)) (car rem) rem)))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list m1 '* m2))))
(define (union-set set1 set2)
(cond ((null? set1) set2)
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else
(adjoin-set (car set1)
(union-set (cdr set1) set2)))))
adjoin-set was changed to allow duplicates.
adjoin-set is sufficiently more efficient, it has a time complexity of $\Theta(1)$ compared to the original $\Theta(n)$ .
The set allowing duplicates is suitable for situations that require frequent adjoin operations.
(define (element-of-set? x set)
(if (null? set)
#f
(or (equal? x (car set))
(element-of-set? x (cdr set)))))
(define (adjoin-set x set)
(cons x set))
(define (intersection-set set1 set2)
(cond ((null? set1) '())
((element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1) set2)))
(else (intersection-set (cdr set1) set2))))
(define (union-set set1 set2)
(cond ((null? set1) set2)
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else
(adjoin-set (car set1)
(union-set (cdr set1) set2)))))
Both version have the time complexity of $\Theta(n)$ , but the ordered version has to examine on the average half of the set instead of the entire set.
(define (adjoin-set x set)
(cond ((null? set) (list x))
((= x (car set)) set)
((< x (car set)) (cons x set))
(else (cons (car set) (adjoin-set x (cdr set))))))
(define (union-set set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
((= (car set1) (car set2))
(cons (car set1) (union-set (cdr set1) (cdr set2))))
((< (car set1) (car set2))
(cons (car set1) (union-set (cdr set1) set2)))
(else
(cons (car set2) (union-set set1 (cdr set2))))))
a. Trees in Figure 2.16 can be represented as
(define tree1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
(define tree2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))))
(define tree3 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ()))))
Both procedures evaluate to the same list (1 3 5 7 9 11) .
b. tree->list2 grows slower.
For tree->list1 ,
$$T(n)=2\cdot T(n/2)+\Theta(n)\,,$$
where $\Theta(n)$ means that append takes linear time to combime two lists; and the recurrence has the solution $T(n)\sim\Theta(n\log n)$ .
For tree->list2 ,
$$T(n)=2\cdot T(n/2)+\Theta(1)\,,$$
since it uses a single cons to combine the results; and the recurrence has the solution $T(n)\sim\Theta(n)$ .
Actually, I looked up the solutions to the recurrences, since I’m not able to solve such equations at present. I will come back to explain them once I finished reading related topics in Concrete Mathematics.
a. The generated tree looks like
5
/ \
1 9
\ / \
3 7 11
The partial-tree procedure split the list into three parts and combine them into a tree. For example, the list (1 3 5 7 9 11) would be split into parts:
(1 3) of the length left-size , which is used to generate the left-tree ;5 as this-entry , the entry of the generated tree;(7 9 11) of the length right-size , which is used to generate the right-tree .Then the parts would be combined like (this-entry left-tree right-tree) .
b. Suppose we’re going to convert a list of length $n$ into a tree.
The list->tree procedure depends on (partial-tree <list> n) , which generates two partial-tree of the lengths of about half of $n$ , and combine them into a tree. The combining step uses list which requires a constant time. Then we have the recurrence
$$T(n)=2\cdot T(n/2)+\Theta(1)\,,$$
which has the solution $T(n)\sim\Theta(n)$ .
Implemented using previously defined procedures. union-set-as-list is the original union-set ; intersection-set-as-list is the original intersection-set .
(define (union-set set1 set2)
(let ((list1 (tree->list set1))
(list2 (tree->list set2)))
(list->tree (union-set-as-list list1 list2))))
(define (intersection-set set1 set2)
(let ((list1 (tree->list set1))
(list2 (tree->list set2)))
(list->tree (intersection-set-as-list list1 list2))))
(define (lookup given-key set-of-records)
(cond ((null? set-of-records) #f)
((equal? given-key (key (entry set-of-records))) (entry set-of-records))
((< given-key (key (entry set-of-records)))
(lookup x (left-branch set-of-records)))
((> given-key (key (entry set-of-records)))
(lookup x (right-branch set-of-records)))))
The result is (A D A B B C A) .
(define (encode-symbol symbol tree)
(if (leaf? tree)
'()
(cond ((element-of-set? symbol (symbols (left-branch tree)))
(cons 0 (encode-symbol symbol (left-branch tree))))
((element-of-set? symbol (symbols (right-branch tree)))
(cons 1 (encode-symbol symbol (right-branch tree))))
(else (error "bad symbol: ENCODE-SYMBOL" symbol)))))
At first, I wrote a procedure with a helper procedure encode-1 instead of encode-symbol (because I carelessly skipped reading the latter part of the requirements), which is analogous to the decode sample code in the book. This version is faster than a procedure making use of append , since append takes linear time to combine the results instead of constant time.
(define (encode message tree)
(define (symbol->next-bit symbol tree)
(cond ((element-of-set? symbol (symbols (left-branch tree))) 0)
((element-of-set? symbol (symbols (right-branch tree))) 1)
(else (error "bad symbol: SYMBOL->NEXTBIT" symbol))))
(define (encode-1 symbols current-branch)
(if (null? symbols)
'()
(let ((next-bit
(symbol->next-bit (car symbols) current-branch)))
(let ((next-branch
(choose-branch next-bit current-branch)))
(cons next-bit
(if (leaf? next-branch)
(encode-1 (cdr symbols) tree)
(encode-1 symbols next-branch)))))))
(encode-1 message tree))
(define (successive-merge set)
(if (null? (cdr set))
(car set)
(successive-merge
(adjoin-set (make-code-tree (car set) (cadr set))
(cddr set)))))
$84$ bits are needed using Huffman encoding method; $108$ bits are needed using fixed-length code.
Such trees look like
/\
/\ 2^(n-1)
/\ 2^(n-2)
/\ ...
1 2
The most frequent symbol requires one bit to represent; and the least frequent symbols require $n-1$ bits to represent.
Encoding the most frequent symbol, we have to search through the entire symbol list once, which takes linear time. Thus
$$T(n)\sim\Theta(n)\,.$$
Encoding a least frequent symbol, we have to search through a list containing $n$ symbols, then a list containing $n-1$ symbols, then a list containing $n-2$ symbols, till we reach the bottom of the tree. Thus
$$T(n)\sim\Theta(n^2)\,.$$