练习2.17
(define (last-pair l)
(if (null? (cdr l))
l
(last-pair (cdr l))))
练习2.18
(define (reverse1 lst)
(if (null? lst)
'()
(append (reverse1 (cdr lst)) (list (car lst)))))
练习2.19
(define (cc amount coin-values)
(cond ((= amount 0) 1)
((or (< amount 0) (no-more? coin-values)) 0)
(else
(+ (cc amount (except-first-denomination coin-values))
(cc (- amount (first-denomination coin-values)) coin-values)))))
(define (first-denomination x) (car x))
(define (except-first-denomination x) (cdr x))
(define (no-more? x) (null? x))
练习2.20
(define (same-parity . n)
(define (same d)
(or (and (even? d) (even? (car n)))
(and (odd? d) (odd? (car n)))))
(define (iter i)
(cond
((null? i) '())
((same (car i))
(cons (car i) (iter (cdr i))))
(else (iter (cdr i)))))
(iter n))
练习2.21
(define (square x) (* x x))
(define (square-list items)
(if (null? items)
'()
(cons (square (car items)) (square-list (cdr items)))))
(define (square-list2 items)
(map square items))
练习2.22
- cons拼接的顺序错误
- 拼接方法错误，应该使用append 追加到最后而不是使用cons拼接
可修改为：
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(append answer
(list (square (car things)))))))
(iter items '()))
练习2.23
(define (for-each f lst)
(when (not (null? lst))
(f (car lst))
(for-each2 f (cdr lst))))
练习2.24
(1 (2 (3 4)))
练习2.25
(car (cdr (car (cdr (cdr '(1 3 (5 7) 9))))))
(car (car '((7))))
(car (cdr (cdr (cdr '(1 (2 (3 (4 (5 (6 7))))))))))
(cadr (cadr (cadr (cadr (cadr (cadr '(1 (2 (3 (4 (5 (6 7))))))))))))
练习2.26
#;142> (define x (list 1 2 3))
#;174> (define y (list 4 5 6))
#;190> (append x y)
(1 2 3 4 5 6)
#;205> (cons x y)
((1 2 3) 4 5 6)
#;218> (list x y)
((1 2 3) (4 5 6))
练习2.27
(define (deep-reverse lst)
(if (pair? lst)
(reverse (map deep-reverse lst))
lst))
练习2.28
(define (fringe tree)
(cond ((pair? tree)
(append (fringe (car tree)) (fringe (cdr tree))))
((null? tree) tree)
(else (list tree))))
练习2.29
a)
(define (left-branch m) (car m))
(define (right-branch m) (cadr m))
(define (branch-length b) (car b))
(define (branch-structure b) (cadr b))
b)
(define (mobile? b) (pair? (branch-structure b)))
(define (branch-weight b)
(if (mobile? b)
(total-weight (branch-structure b))
(branch-structure b)))
(define (total-weight m)
(+ (branch-weight (left-branch m))
(branch-weight (right-branch m))))
c)
(define (balance? m)
(let ((l (left-branch m))
(r (right-branch m)))
(and (= (* (branch-length l) (branch-weight l))
(* (branch-length r) (branch-weight r)))
(if (branch? r) (balance? r) #t)
(if (branch? l) (balance? l) #t))))
d) 因为其他计算中都使用了题目a当中使用的封装实现，不关心结构实现细节，只需要修改题目a当中的部分函数就可以适应新的变化
练习2.30
(define (square-tree t)
(cond ((pair? t)
(cons (square-tree (car t)) (square-tree (cdr t))))
((null? t) '())
(else (square t))))
(define (square-tree2 t)
(if (pair? t)
(map square-tree2 t)
(square t)))
练习2.31
(define (tree-map f t)
(define (iter t)
(if (pair? t)
(map square-tree2 t)
(f t)))
(iter t))
运行结果：
#;2390> (tree-map square (list 1 (list 2 (list 3 4) 5) (list 6 7)))
(1 (4 (9 16) 25) (36 49))
练习2.32
(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (r) (append r (list (car s)))) rest)))))
练习2.33
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (map2 p sequence)
(accumulate (lambda (x y) (cons (p x) y)) nil sequence))
(define (append2 seq1 seq2)
(accumulate cons seq2 seq1))
(define (length2 sequence)
(accumulate (lambda (x y) (+ y 1)) 0 sequence))
练习2.34
(define (horner-eval x coefficient-sequence)
(accumulate (lambda (this-coeff higher-terms)
(* x (+ this-coeff higher-terms))) 0 coefficient-sequence))
练习2.35
(define (count-leaves t)
(accumulate + 0 (map (lambda (x) (if (pair? x) (count-leaves x) 1)) t)))
练习2.36
(define (accumulate-n op init seqs)
(if (null? (car seqs))
'()
(cons (accumulate op init (map car seqs))
(accumulate-n op init (map cdr seqs)))))
练习2.37
(define (dot-product v w)
(accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
(map (lambda (x) (dot-product x v)) m))
(define (transpose mat)
(accumulate-n cons '() mat))
(define (matrix-*-matrix m n)
(let ((cols (transpose n)))
(map (lambda (x) (matrix-*-vector cols x)) m)))
练习2.38
根据运算符的向左结合和向又结合不同而导致不同结果。
要想得到相同结果需要运算符满足结合律
既： (op (op a b) c) == (op a (op b c))
练习2.39
(define (reverse-right sequence)
(fold-right (lambda (x y) (append y (list x))) nil sequence))
(define (reverse-left sequence)
(fold-left (lambda (x y) (cons y x)) nil sequence))
练习2.40
(define (enumerate-interval low high)
(if (> low high)
'()
(cons low (enumerate-interval (+ low 1) high))))
(define (unique-pairs n)
(accumulate append
'()
(map (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n))))
(define (prime-sum? pair)
(prime? (+ (car pair) (cadr pair))))
(define (make-pair-sum pair)
(list (car pair) (cadr pair) (+ (car pair) (cadr pair))))
(define (prime-sum-pairs n)
(map make-pair-sum
(filter prime-sum?
(unique-pairs n))))
练习2.41
(define (flatmap proc seq)
(accumulate append '() (map proc seq)))
(define (unique-triples n)
(flatmap (lambda (i)
(map (lambda (j)
(reverse (cons i j)))
(unique-pairs (- i 1))))
(enumerate-interval 1 n)))
练习2.42
八皇后问题中，每个棋盘上的皇后用(cons row col) 表示。
一个棋盘用list表示，每个元素为一个皇后。
判断两个皇后冲突conflict?方法为：
- 行冲突： 两个皇后的
row相同 - 列冲突： 两个皇后的
col相同 - 正斜冲突：两个皇后的
col+row相同 - 反斜冲突：两个皇后的
col-row相同
由此完整程序为：
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
(define empty-board (list))
(define (adjoin-position row col positions)
(cons (cons row col) positions))
(define (safe? k positions)
(define (conflict? x y)
(or (= (car x) (car y))
(= (cdr x) (cdr y))
(= (+ (car x) (cdr x))
(+ (car y) (cdr y)))
(= (- (car x) (cdr x))
(- (car y) (cdr y)))))
(let ((new (car positions))
(rest (cdr positions)))
(= 0 (length (filter (lambda (x) (conflict? new x)) rest)))))
练习2.43
ex-2.42的执行是先执行(queen-cols (- k 1)) 干后根据其中每个结果执行broad-size次 adjoin-position 计算。
Louis 的计算是broad-size次执行(queen-cols (- k 1)) 计算，并根据其中每个结果执行adjoin-position计算。但是每次执行(queen-cols (- k 1)) 计算的时候会再次执行broad-size次相当于(queen-cols (- k 2))的计算，所以假设ex-2.42的计算时间为则Louis的计算时间为：