这一节的内容非常有趣，通过将序列作为interface，在此基础上进而提取出各种高阶操作（map,filter,accumulate,enumerate等），由此引出模块化设计的讨论。模块化设计带来复杂性的降低，同时可能引入性能上的损失，比如书中对sum-odd-squares过程的两种写法，原来的写法枚举列表元素的过程散落在累积、过滤、映射的过程中，主要一次循环就够了，而通过三个高阶过程来操作反而需要3次的遍历。
习题2.33，将map,append,length基本过程用累积操作重新定义，联系以往的实现通过观察和测试可以得出：
(define (map p sequence) (accumulate (
lambda
(x y) (cons (p x) y)) () sequence)) (define (append seq1 seq2) (accumulate cons seq2 seq1)) (define (length sequence) (accumulate (
lambda
(x y) (
+
1
y)) 0 sequence))
难点就在于累积的操作。
习题2.34，Horner规则求多项式，难点也是累积操作的定义：
(define (horner
-
eval x coefficient
-
sequence) (accumulate (
lambda
(this
-
coeff higher
-
terms) (
+
this
-
coeff (
*
x higher
-
terms))) 0 coefficient
-
sequence))
只要记住lambda中的y其实是另一个递归的accumulate就比较容易完成了。
测试下:
>
(horner
-
eval
2
(list
1
3
0
5
0
1
))
79
习题2.35，利用map和accumulate重新定义count-leaves统计树的节点数目：
(define (count
-
leaves t) (accumulate
+
0 (map (
lambda
(x) (
if
(pair? x) (count
-
leaves x)
1
)) t)))
map过程的参数op是过程
(lambda (x) (if (pair? x) (count-leaves x) 1))
当x是列表，递归调用count-leaves，否则返回个数1
习题2.36，列表的列表，因此map过程的第一个参数是一个过程作用于列表中的每个列表，当然是采用car将它们首项取出然后进行op操作，因此：
(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，list作为Lisp的基本结构可以演化出各式各样的复杂结构，比如此题就将列表作为矢量，矢量通过组合成为矩阵，3个解答就是矩阵的运算：
(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，计算下结果：
>
(fold
-
right
/
1
(list
1
2
3
))
1
1
/
2
;也就是3
/
2
>
(fold
-
left
/
1
(list
1
2
3
))
1
/
6
>
(fold
-
right list () (list
1
2
3
)) (
1
(
2
(
3
())))
>
(fold
-
left list () (list
1
2
3
)) (((()
1
)
2
)
3
)
如果想使这两个过程的结果相同，op需要满足交换率和结合率的条件。
习题2.39:
;
2.39
(define (reverse
-
list sequence) (fold
-
right (
lambda
(x y)(append y (list x))) () sequence)) (define (reverse
-
list2 sequence) (fold
-
left (
lambda
(x y) (cons y x)) () sequence))
文章转自庄周梦蝶 ，原文发布时间5.17
相关资源：敏捷开发V1.0.pptx
