2.27
(define (deep-reverse lst)
(define (iter lst-o lst-d)
(cond ((null? lst-o)
lst-d)
((not (pair? (car lst-o)))
(iter (cdr lst-o)
(cons (car lst-o) lst-d)))
(else
(iter (cdr lst-o)
(cons (deep-reverse (car lst-o))
lst-d)))))
(iter lst null))
2.28
(define (fringe x)
(define (iter tree lst)
(cond ((null? tree) lst)
((not (pair? tree)) (cons tree lst))
(else (iter (car tree) (iter (cdr tree) lst)))))
(iter x null))
2.30
(define (square-tree- x)
(cond ((null? x) null)
((not (pair? x)) (* x x))
(else (cons (square-tree- (car x))
(square-tree- (cdr x))))))
(define (square-tree x)
(map (lambda(subtree)
(if (pair? subtree)
(square-tree subtree)
(* subtree subtree)))
x))
2.31
(define (tree-map proc tree)
(map (lambda(subtree)
(if (pair? subtree)
(tree-map proc subtree)
(proc subtree)))
tree))
(define (square-tree+ tree)
(tree-map (lambda(x) (* x x)) tree))
2.32
(define (subsets s)
(if (null? s)
(list null)
(let ((rest (subsets (cdr s))))
(append rest (map (lambda(x) (cons (car s) x)) rest)))))
和換零錢問(wèn)題的思路是一樣的，對(duì)于一個(gè)集合的所有子集的集合，可以分為兩部分，含有第一個(gè)元素和不含第一個(gè)元素的集合。而且含第一個(gè)元素的所有子集除去第一個(gè)元素，恰好正是所有不含第一個(gè)元素的子集。
也可以換個(gè)思路，對(duì)于集合A，設(shè)它可以表示為 (a1)∪(a2,...,an) ，而 (a2,...,an) 的所有子集的集合是 B=(B1,...Bm),那么可以證明A的所有子集的集合 C=B∪((A1)∪B1,(A1)∪B2,...,(A1)∪Bm);
證明：設(shè) X 是 A 的一個(gè)子集，那么如果 a1∈X，那么 X∈((A1)∪B1,(A1)∪B2,...,(A1)∪Bm)，否則X∈B，所以
X∈C