SICP 习题参考答案 2.3

win_hate

只要把两个选择函数略为修改就可以了：

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

复制代码

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

复制代码

前缀表达式不是很好看。对比一下 maxima 的微分

1. 
   
2. (%i1) diff(x*y*(x+3), x);
   
3. (%o1)                           (x + 3) y + x y
   

复制代码

[ 本帖最后由 win_hate 于 2008-10-29 10:15 编辑 ]

win_hate

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?

win_hate

把 a, b 一起做了。

• 这个题目并没有看上去那么难。因为只有两种运算，而且 scheme 天生具有处理括号的能力，所以不用考虑括号平衡的问题。
  
• 为了去除多余的括号，比如 (x), ((x+y))，加进了一个 strip 函数
  
• 为了 make-product 和 make-sum 不产生多余的括号，相应的代码有点胖
  
• 满足了题目 “只修改建构函数和选择函数，不改动 deriv" 的要求。
  

1. 
   
2. (define (strip exp)
   
3.   (if (and (list? exp) (null? (cdr exp)))
   
4.       (strip (car exp))
   
5.       exp))
   
6. 
   
7. (define (sum? s)
   
8.   (member '+ s))
   
9. 
   
10. (define (addend s)
    
11.   (define (f ini xs)
    
12.     (let ((x (car xs)))
    
13.       (if (eq? x '+)
    
14.           ini
    
15.           (f (append ini (list x)) (cdr xs)))))
    
16.   (strip (f '() s)))
    
17.   
    
18. (define (augend s)
    
19.   (strip (cdr (member '+ s))))
    
20. 
    
21. (define (product? s)
    
22.   (and (member '* s) (not (member '+ s))))
    
23. 
    
24. (define (multiplier p)
    
25.   (strip (car p)))
    
26. 
    
27. (define (multiplicand p)
    
28.   (strip (cddr p)))
    
29. 
    
30. (define (make-sum a1 a2)
    
31.   (cond ((=number? a1 0) (strip a2))
    
32.         ((=number? a2 0) (strip a1))
    
33.         ((and (number? a1) (number? a2)) (+ a1 a2))
    
34.         (else (let ((A1 (if (list? a1) a1 (list a1)))
    
35.                     (A2 (if (list? a2) a2 (list a2))))
    
36.                 (append A1 (cons '+ A2))))))
    
37. 
    
38. (define (make-product m1 m2)
    
39.   (cond ((or (=number? m1 0) (=number? m2 0)) 0)
    
40.         ((=number? m1 1) (strip m2))
    
41.         ((=number? m2 1) (strip m1))
    
42.         ((and (number? m1) (number? m2)) (* m1 m2))
    
43.         (else (let ((M1 (if (list? m1)
    
44.                             (if (sum? m1) (list m1) m1)
    
45.                             (list m1)))
    
46.                     (M2 (if (list? m2)
    
47.                             (if (sum? m2) (list m2) m2)
    
48.                             (list m2))))
    
49.                 (append M1 (cons '* M2))))))
    

复制代码

演示：

1. 
   
2. > (deriv '(x + 3) 'x)
   
3. 1
   
4. 
   
5. > (deriv '(x * y) 'x)
   
6. y
   
7. 
   
8. > (deriv '( x * y * ( x + 3)) 'x)
   
9. (x * y + y * (x + 3))
   
10. 
    
11. > (deriv '(x + (3 * (x + (y + 2)))) 'x)
    
12. 4
    
13. 
    
14. > (deriv '(x + 3 * (x + y + 2)) 'x)
    
15. 4
    

复制代码

[ 本帖最后由 win_hate 于 2008-10-29 09:52 编辑 ]

win_hate

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

win_hate

1. 
   
2. (define (union-set set1 set2)
   
3.   (if (null? set1) set2
   
4.       (union-set (cdr set1)
   
5.                 (adjoin-set (car set1) set2))))
   

复制代码

[ 本帖最后由 win_hate 于 2008-10-30 23:19 编辑 ]

win_hate

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?

win_hate

1. 
   
2. (define (adjoin-set x set)
   
3.   (cons x set))
   
4. 
   
5. (define (union-set set1 set2)
   
6.   (append set1 set2))
   

复制代码

其它函数不变。adjoin 变成 O(1) 的了。 union-set 的效率与 set1 的长度成线性关系。作用在相同集合上时，其它函数效率不变。但由于构造出来的数据含有重复的元素，会引会引发数据膨胀。

[ 本帖最后由 win_hate 于 2008-10-30 23:29 编辑 ]

win_hate

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.

win_hate

1. 
   
2. (define (adjoin-set x set)
   
3.   (if (null? set) (cons x '())
   
4.       (let ((y (car set)))
   
5.         (cond ((= x y) set)
   
6.               ((> x y) (cons y (adjoin-set x (cdr set))))
   
7.               (else (cons x set))))))
   

复制代码

书本上 “requires on the average about half as many steps” 疑有误。已排序的情况下，查找的次数是少了，但对插入元素的位置有要求。构造新表的开销比无需排序时大。

win_hate

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