SICP 2.2 层级数据和闭包属性 · 拖鞋党的拖鞋摊

好久没填坑都快忘了……

笔记

cons 可以嵌套

(cons 1 (cons 2 (cons 3 (cons 4 nil)))) 相当于 list(1 2 3 4)

那 (cons 1 (cons 2 (cons 3 4))) 呢？

原来 nil 来源于意大利语 nihil ，意为无，没有。

cons 还可用于在列表前面附加元素

1 2	(cons 10 (list 1 2 3 4)) ; (10 1 2 3 4)

那要在列表后面附加元素呢，使用 append

(append (list 1 2) (list 3 4))
; (1 2 3 4)
;; 如果第二个不是列表而是一个元素的话，结果会是 cons
(append (list 1 2) 3)
; (1 2 . 3)

用 null? 来判断列表是否为空。（为什么不是 nil? ……）

((1 2) 3 4) 可以看成 (cons (list 1 2) (list 3 4))

也可以看成树状结构，取决于目标和解释方式。

在递归的过程中有时候需要判断参数是不是 pair 。可以用 pair? 来判断。

习题

习题 2.17

Exercise 2.17. Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:

1 2	(last-pair (list 23 72 149 34)) (34)

列表就是一系列的 pair 。最后一个元素一定处于 (cons xxx nil) 的类似列表。所以通过基本的操作 car 和 cdr 不断的取尾，最后一个元素为 nil 时所处的 pair 第一个元素就是整个列表的最后一个元素。最后再用 list 封装以达到题目要求。

(define (last-pair alist)
  (if (null? (cdr alist))
      (list (car alist))
      (last-pair (cdr alist))))

测试

(last-pair (list 1 2 3 4))
; => (4)
(last-pair (list 1))
; => (1)
(last-pair (list 23 72 149 34))
; => (34)

习题 2.18

Exercise 2.18. Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:
1
2
(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

因为列表是一个递归嵌套 pair 的结构，所以很自然要用递归的方式处理。

用递归的方式处理，最基本的是先确定递归退出条件。通常是考虑最小子问题。

在这个例子中，最小的列表是空列表。

逆转空列表结果还是空列表。

接着就是找递归的递进条件，也就是怎么把问题变成更小的问题。

考虑到一个列表可以拆分为第一个元素和剩余列表。

那么逆转一个列表，相当于逆转过后的剩余列表拼接上第一个元素。

这样问题的规模就缩小了。只要同样地逆转剩余列表即可。

(define (reverse alist)
  (if (null? alist)
      alist
      (append (reverse (cdr alist)) 
              (list (car alist)))))

测试

(reverse (list 1 2 3 4))
; => (4 3 2 1)
(reverse (list 1 4 9 16 25))
; => (25 16 9 4 1)

习题 2.19

Exercise 2.19. Consider the change-counting program of section 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure first-denomination and partly into the procedure count-change (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:
1
2
(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

We could then call cc as follows:
1
2
(cc 100 us-coins)
292

To do this will require changing the program cc somewhat. It will still have the same form, but it will access its second argument differently, as follows:

(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 the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

题目要求实现 first-denomination 、except-first-denomination 和 no-more? 。

其实函数名字已经提示很多了。

first-denomination 是取第一个货币单位。

except-first-denomination 是排除第一个货币单位。

no-more? 是判断是否还有货币单位。

参考列表的操作，很容易写出来

1
2
3

(define except-first-denomination cdr)
(define first-denomination car)
(define no-more? null?)

测试

(cc 100 us-coins)
; => 292
(cc 100 uk-coins)
; => 104561

题目还问改变货币列表中的顺序是否会影响结果。

考虑到换零钱的计算方式是换某种货币的组合数加上不换某种货币的组合数。

显然换 100 加上不换 100 的组合等于换 5 加上不换 5 的组合。因为要兑换的总额是一样的。

(define us-coins2 (list 1 5 10 25 50))
(cc 100 us-coins2)
; => 292
(cc 100 us-coins)
; => 292

习题 2.20

Exercise 2.20. The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter’s value will be a list of any remaining arguments. For instance, given the definition
1
(define (f x y . z) <body>)

the procedure f can be called with two or more arguments. If we evaluate
1
(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition
1
(define (g . w) <body>)

the procedure g can be called with zero or more arguments. If we evaluate
1
(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).11

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,
1
2
3
4
(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)
(same-parity 2 3 4 5 6 7)
(2 4 6)

题目介绍了不定参数的函数定义方式，通过类似 pair 的形式来定义，还是很有趣的。

same-parity 肯定要支持不定参数。那么最少有几个参数？

是 1 个。如果是 1 个直接返回该元素即可。

所以 same-parity 的定义如下

1
2
3

(define (same-parity element . alist) <body>)

; 点两边都要有空格，不然会视作函数名为 same-parity.alist 的函数。

第一个参数是 alist 的第一个元素。

第二个参数是剩余的列表。

然后考虑如何把子问题规模缩小。

比如对于列表 (1 2 3 4)

可以拆分为 (same-parity 1 2) 和 (same-parity 1 (3 4))

这样问题的规模就变小了。

因为 (same-parity 1 2) 会把参数收集为列表，这样递归不是很方便，所以创建一个 (same-parity-iter) 。

完整代码如下

(define (same-parity . alist)
  (define (same-parity-iter first rest result)
    (if (null? rest)
        result
        (if (same-parity? first (car rest))
            (same-parity-iter first (cdr rest) (append result (list (car rest))))
            (same-parity-iter first (cdr rest) result))))
  (if (or (= (length alist) 0)
          (= (length alist) 1))
      alist
      (same-parity-iter (car alist) (cdr alist) (list (car alist)))))
      
(define (same-parity? a b)

  (or (and (even? a) (even? b))

      (and (odd? a) (odd? b))))

测试

(same-parity 1 2 3 4 5 6 7)
; => (1 3 5 7)
(same-parity 2 3 4 5 6 7)
; => (2 4 6)

习题 2.21

Exercise 2.21. The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.
1
2
(square-list (list 1 2 3 4))
(1 4 9 16)

Here are two different definitions of square-list. Complete both of them by filling in the missing expressions:
1
2
3
4
5
6
(define (square-list items)
  (if (null? items)
      nil
      (cons <??> <??>)))
(define (square-list items)
  (map <??> <??>))

仿照 scale-list 即可得到答案

第一种

(define (square-list items)
  (if (null? items)
      nil
      (cons (* (car items) (car items)) (square-list (cdr items)))))

第二种

1 2	(define (square-list items) (map (lambda (x) (* x x)) items))

习题 2.22

Exercise 2.22. Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:

(define (square-list items)
  (define (iter things answer)
  (if (null? things)
      answer
      (iter (cdr things) 
            (cons (square (car things))
                  answer))))
  (iter items nil))

Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?

Louis then tries to fix his bug by interchanging the arguments to cons:
1
2
3
4
5
6
7
8
(define (square-list items)
  (define (iter things answer)
  (if (null? things)
      answer
      (iter (cdr things)
            (cons answer
                  (square (car things))))))
  (iter items nil))

This doesn’t work either. Explain.

这么做显然是有问题的。用 Applicative Order 展开就清楚了

(square-list (list 1 2 3))
(iter (list 1 2 3) nil)
(iter (list 2 3) (cons 1 nil))
(iter (list 2 3) (list 1))
(iter (list 3) (cons 4 (list 1)))
(iter (list 3) (list 4 1))
(iter nil (cons 9 (list 4 1)))
(iter nil (list 9 4 1))
; (9 4 1)

再看修正版，还是使用 Applicative Order 展开

(square-list (list 1 2 3))
(iter (list 1 2 3) nil)
(iter (list 2 3) (cons nil 1))
(iter (list 3) (cons (cons nil 1) 4))
(iter nil (cons (cons (cons nil 1) 4) 9))
; (((1) . 4) . 9)

这次他虽然调整了顺序，但是没有使用正确的方式附加元素。

按照提供的现有函数，如果想在列表后面附加元素应该使用 append 和 list

1 2	(append (list 1 2 3) (list 4)) ; => (1 2 3 4)

所以这么改就可以了。

(define (square-list items)
  (define (iter things answer)
  (if (null? things)
      answer
      (iter (cdr things)
            (append answer
                  (list (square (car things)))))
  (iter items nil))

测试

1
2
3

(square-list (list 1 2 3 4))

; => (1 4 9 16)

习题 2.23

Exercise 2.23. The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all – for-each is used with procedures that perform an action, such as printing. For example,
1
2
(for-each (lambda (x) (newline) (display x))
 (list 57 321 88))

573
21
88

The value returned by the call to for-each (not illustrated above) can be something arbitrary, such as true. Give an implementation of for-each.

比起 map ，for-each 更注重操作的副作用，而不是结果。

所以如果不介意返回值的话，完全可以把 map 当作 for-each

1	(define for-each map)

如果自己写是这样的。

(define (for-each f alist)
  (if (null? alist)
      #t
      (list  (for-each f (cdr alist)) (f (car alist)))))

注意把 (f (car alist)) 放在后面，因为参数求值从后面开始。

习题 2.24

Exercise 2.24. Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-and-pointer structure, and the interpretation of this as a tree (as in figure 2.6).

表达式的结果是

1
2
3

(list 1 (list 2 (list 3 4)))

; => (1 (2 (3 4)))

盒子图

+---+---+      +---+---+

|   |   | +--> |   |   |

+-+-+---+      +-+-+---+

  |              |

  v              v

+---+---+      +---+---+       +---+---+

|   |   |      |   |   | +---> |   |   |

+-+-+---+      +-+-+---+       +-+-+---+

  |              |               |

  v              v               v

+---+---+      +---+---+       +---+---+      +---+---+

|   |   |      |   |   |       |   |   | +--> |   |   |

+-+-+---+      +-+-+---+       +-+-+---+      +-+-+---+

  |              |               |              |

  v              v               v              v

+-+             +-+             +-+            +-+

|1|             |2|             |3|            |4|

+-+             +-+             +-+            +-+

树状图

(1 (2 (3 4)))
├─1
└──(2 (3 4))
    ├──2
    └──(3 4)
        ├──3
        └──4

习题 2.25

Exercise 2.25. Give combinations of cars and cdrs that will pick 7 from each of the following lists:
1
2
3
4
5
(1 3 (5 7) 9)

((7))

(1 (2 (3 (4 (5 (6 7))))))

由内往外，一步步使用 car 和 cdr 即可。

比如对于(1 3 (5 7) 9) 先从 (5 7)下手。

想要得到 (5 7) 中的 7 只需要 (car (cdr (5 7))

对于 (1 3 (5 7) 9) 先要 cdr 得到 (3 (5 7) 9)

然后再 cdr 得到 ((5 7) 9)

再 car 一下就能得到 (5 7)了。

所以答案如下

; (1 3 (5 7) 9)
(car (cdr (car (cdr (cdr (list 1 3 (list 5 7) 9))))))
; ((7))
(car (car (list (list 7))))
; (1 (2 (3 (4 (5 (6 7))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7))))))))))))))))))

要注意 cdr 始终返回一个列表，所以 (cdr (5 (6 7))) 是 ((6 7)) 不是 (6 7) 。

习题 2.26

Exercise 2.26. Suppose we define x and y to be two lists:
1
2
(define x (list 1 2 3))
(define y (list 4 5 6))

What result is printed by the interpreter in response to evaluating each of the following expressions:
1
2
3
(append x y)
(cons x y)
(list x y)

答案如下

(define x (list 1 2 3))
(define y (list 4 5 6))
(append x y)
; => (1 2 3 4 5 6)
(cons x y)
; => ((1 2 3) 4 5 6)
(list x y)
; => ((1 2 3) (4 5 6))

习题 2.27

Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all subsists deep-reversed as well. For example,
1
2
3
4
5
6
7
(define x (list (list 1 2) (list 3 4)))
x
((1 2) (3 4))
(reverse x)
((3 4) (1 2))
(deep-reverse x)
((4 3) (2 1))

首先定义规则，深度反转空列表还是空列表。

深度反转单个叶子节点还是单个叶子节点。

深度反正一棵树等于反转剩余列表拼接上反转第一个列表。

翻译成代码

(define (deep-reverse tree)
  (cond ((null? tree) ())
        ((not (pair? tree)) (list tree))
        (else (append (deep-reverse (cdr tree))
                      (deep-reverse (car tree))))))

测试

1
2
3

(define x (list (list 1 2) (list 3 4)))
(deep-reverse x)
; => ((4 3) (2 1))

习题 2.28

Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

(define x (list (list 1 2) (list 3 4)))

(fringe x)
(1 2 3 4)

(fringe (list x x))
(1 2 3 4 1 2 3 4)

类似上一题， fringe 空列表为空列表

fringe 单个元素为单个元素。

fringe 一棵树为fringe 第一个列表拼接上 fringe 剩余元素。

翻译成代码

(define (fringe tree)
  (cond ((null? tree) ())
        ((not (pair? tree)) (list tree))
        (else (append (fringe (car tree))
                      (fringe (cdr tree))))))

测试

(define x (list (list 1 2) (list 3 4)))
(fringe x)
; => (1 2 3 4)
(fringe (list x x))
; => (1 2 3 4 1 2 3 4)

习题 2.29

Exercise 2.29. A binary mobile consists of two branches, a left branch and a right branch. Each branch is a rod of a certain length, from which hangs either a weight or another binary mobile. We can represent a binary mobile using compound data by constructing it from two branches (for example, using list):

1 2	(define (make-mobile left right) (list left right))

A branch is constructed from a length (which must be a number) together with a structure, which may be either a number (representing a simple weight) or another mobile:

1 2	(define (make-branch length structure) (list length structure))

a. Write the corresponding selectors left-branch and right-branch, which return the branches of a mobile, and branch-length and branch-structure, which return the components of a branch.

b. Using your selectors, define a procedure total-weight that returns the total weight of a mobile.

c. A mobile is said to be balanced if the torque applied by its top-left branch is equal to that applied by its top-right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Design a predicate that tests whether a binary mobile is balanced.

d. Suppose we change the representation of mobiles so that the constructors are

(define (make-mobile left right)
  (cons left right))
(define (make-branch length structure)
  (cons length structure))

How much do you need to change your programs to convert to the new representation?

问题 a 。只需要看数据结构的定义，所以四个选择器的定义如下

(define left-branch car)
(define (right-branch tree) (car (cdr tree)))
(define branch-length car)
(define (branch-structure branch) (car (cdr branch)))

接着实现问题 b 要求的 total-weight 。

分支的最基本类型是形如 (5 3) 这种第一个是长度，第二个是重量的类型。

这种情况分支的重量为 3

其他情况下分支的重量等于左子树的重量加上右子树的重量。

(define (total-weight mobile)
  (if (not (pair? mobile))
      mobile
      (+ (total-weight (branch-structure (left-branch mobile)))
         (total-weight (branch-structure (right-branch mobile))))))

测试

(define l (make-branch 3 4))
(define r (make-branch 6 7))
(define s (make-branch 1 2))
(define x (make-mobile s (make-branch 7 (make-mobile l r))))
x
; => ((1 2) (7 ((3 4) (6 7))))
(total-weight x)
; => 13
(total-weight (make-mobile l r))
; => 11

问题 c 中定义平衡为所有的左右子数长度和重量的乘积相等。

对于最基本的 mobile 比如 2 。因为没有左右子树，所以认为是相等的。

对于其他的 mobile 比如 ((1 2) (3 4)) 判断左右重量和长度的乘积是否相等。

(define (balanced? mobile)
  (if (not (pair? mobile))
      #t
      (= (* (branch-length (left-branch mobile))
            (total-weight (branch-structure (left-branch mobile))))
         (* (branch-length (right-branch mobile))
            (total-weight (branch-structure (right-branch mobile)))))))

测试

(define l (make-branch 3 4)) 
(define r (make-branch 6 7)) 
(define s (make-branch 1 2)) 
(define x (make-mobile s (make-branch 7 (make-mobile l r))))
(balanced? x)
; => #f
(balanced? (make-mobile l l))
; => #t
(balanced? (make-mobile r r))
; => #t
(balanced? (make-mobile (make-branch 3 4) (make-branch 2 6)))
; => #t

问题 d 。如果改变了定义中的数据结构，需要改动哪些。

基本的选择子肯定要改，还有要改的地方是 total-weight 和 balanced? 中判断是否为最基本的 mobile 的语句。

也就是 (not (pair? mobile)) 。

之所以要该这里是因为这里没有引入抽象屏障，total-weight 和 balanced? 知道了 mobile 的实现。

习题 2.30

Exercise 2.30. Define a procedure square-tree analogous to the square-list procedure of exercise 2.21. That is, square-list should behave as follows:

(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
(1 (4 (9 16) 25) (36 49))

Define square-tree both directly (i.e., without using any higher-order procedures) and also by using map and recursion.

仿照 scale-tree 来做即可。

第一种，不使用高阶函数的类型

(define (square-tree tree)
  (cond ((null? tree) ())
        ((not (pair? tree)) (square tree))
        (else (cons (square-tree (car tree))
                    (square-tree (cdr tree))))))

第二种，使用 map

(define (square-tree tree)
  (map (lambda (sub-tree)
        (if (not (pair? sub-tree))
            (square sub-tree)
            (square-tree sub-tree)))
      tree))

习题 2.31

Exercise 2.31. Abstract your answer to exercise 2.30 to produce a procedure tree-map with the property that square-tree could be defined as

1	(define (square-tree tree) (tree-map square tree))

只要照着上题把用到 square 的替换即可。

(define (tree-map f tree)
  (map (lambda (sub-tree)
        (if (not (pair? sub-tree))
            (f sub-tree)
            (tree-map f sub-tree)))
      tree))

测试

1 2	(square-tree '(1 (2 (3 4) 5) (6 7))) ; => (1 (4 (9 16) 25) (36 49))

习题 2.32

Exercise 2.32. We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))

对于 (subset (list 1 2 3)) 中 rest 为 (subset (list 2 3))

即 ((3) (2) (2 3) () ) 。对比 (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

发现少了 (1) (1 3) (1 2)。

所以需要用 map 把每一个元素拼接成子集。

(define (subsets s)
    (if (null? s)
        (list '())
        (let ((rest (subsets (cdr s))))
            (append rest (map (lambda (x)
                                (cons (car s) x))
                              rest)))))

需要注意的是 () 的子集是 (())。

习题 2.33

Exercise 2.33. Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as accumulations:

(define (map p sequence)
  (accumulate (lambda (x y) <??>) nil sequence))
(define (append seq1 seq2)
  (accumulate cons <??> <??>))
(define (length sequence)
  (accumulate <??> 0 sequence))

注意到 accumulate 中的函数第一个参数 x 是当前 sequance 的值，y 是累积的值。

所以只需要运算后拼接起来就可以了。

1 2	(define (map p sequence) (accumulate (lambda (x y) (cons (p x) y)) nil sequence))

对于 append 只需要将 seq1 中的元素一个个 cons 上去即可。

1 2	(define (append seq1 seq2) (accumulate cons seq2 seq1))

计算长度，每个元素 + 1 长度。

1 2	(define (length sequence) (accumulate (lambda (x y) (+ y 1)) 0 sequence))

习题 2.34

Exercise 2.34. Evaluating a polynomial in $x$ at a given value of $x$ can be formulated as an accumulation. We evaluate the polynomial
$$
a_nr^n + a_{n-1}r^{n-1} + \cdots + a_1r + a_0
$$
using a well-known algorithm called Horner’s rule, which structures the computation as
$$
(\cdots(a_nr + a_{n-1})r + \cdots + a_1)r + a_0
$$
In other words, we start with $a_n$ multiply by $x$, add $a_{n-1}$, multiply by $x$, and so on, until we reach $a_0$.16 Fill in the following template to produce a procedure that evaluates a polynomial using Horner’s rule. Assume that the coefficients of the polynomial are arranged in a sequence, from $a_0$ through $a_n$.

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
              0
              coefficient-sequence))

For example, to compute $1+3x+5x^3+x^5$ at $x = 2$ you would evaluate

(horner-eval 2 (list 1 3 0 5 0 1))

注意到 accumulate 的计算顺序是从右到左。所以只需要重复计算 $a_nr+a_{n-1}$ 即可。

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)   (+ (* higher-terms x)
                                                       this-coeff))
              0
              coefficient-sequence))

测试

(horner-eval 1 (list 1 2 3 4))
; => 10
(horner-eval 2 (list 1 3 0 5 0 1))
; => 79

习题 2.35

Exercise 2.35. Redefine count-leaves from section 2.2.2 as an accumulation:

1 2	(define (count-leaves t) (accumulate <??> <??> (map <??> <??>)))

用 map 遍历数，如果是叶子就长度 + 1，不是就计算叶子数量。这样累加就能得到答案。

(define (count-leaves t)
  (accumulate + 0 (map (lambda (sub-tree)
                         (if (not (pair? sub-tree))
                             1
                             (count-leaves sub-tree)))
                       t)))

习题 2.36

Exercise 2.36. The procedure accumulate-n is similar to accumulate except that it takes as its third argument a sequence of sequences, which are all assumed to have the same number of elements. It applies the designated accumulation procedure to combine all the first elements of the sequences, all the second elements of the sequences, and so on, and returns a sequence of the results. For instance, if s is a sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11 12)), then the value of (accumulate-n + 0 s) should be the sequence (22 26 30). Fill in the missing expressions in the following definition of accumulate-n:

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate op init <??>)
            (accumulate-n op init <??>))))

对于空的序列 (()) 结果为 ()。

对于非空序列 ((1 2) (3 4)) 结果是 (cons (list 1 3) (list 2 4))

所以要得到序列中的每一个元素，使用 map car 。

剩下的类似

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      ()
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

测试

(accumulate-n + 0 '(()))
; => ()
(accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9)))
; => (12 15 18)

习题 2.37

Exercise 2.37. Suppose we represent vectors $v = (v_i)$ as sequences of numbers, and matrices $m = (m_{ij})$ as sequences of vectors (the rows of the matrix). For example, the matrix
$$
\begin{bmatrix}
1 & 2 & 3 & 4\
4 & 5 & 6 & 6\
6 & 7 & 8 & 9
\end{bmatrix}
$$
is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)). With this representation, we can use sequence operations to concisely express the basic matrix and vector operations. These operations (which are described in any book on matrix algebra) are the following:

(dot-product v w) returns the sum $\sum_{i} v_iw_i$

(matrix-*-vector m v) returns the vector $t$, where $t_i = \sum_j m_{ij}v_j$

(matrix-*-matrix m n) returns the matrix $p$, where $p_{ij} = \sum_{k} m_{ik}n_{kj}$

(transpose m) returns the matrix $n$, where $n_{ij} = m_{ji}$

We can define the dot product as17

1 2	(define (dot-product v w) (accumulate + 0 (map * v w)))

Fill in the missing expressions in the following procedures for computing the other matrix operations. (The procedure accumulate-n is defined in exercise 2.36.)

(define (matrix-*-vector m v)
  (map <??> m))
(define (transpose mat)
  (accumulate-n <??> <??> mat))
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map <??> m)))

先看 matrix-*-vector 中 map 后是一个 vector ，根据矩阵和向量乘法的定义，需要两个向量相乘。

所以需要使用 dot-product

1 2	(define (matrix-*-vector m v) (map (lambda (mi) (dot-product v mi)) m))

对于转置 transpose ，每个元素之间只需要 cons

1 2	(define (transpose mat) (accumulate-n cons '() mat))

然后是矩阵相乘，matrix-*-matrix 中的 map 后是一个 vector，而 $n$ 转置后还是一个矩阵。

将转置过后 $n$ 的每一行和 $m$ 每一行相乘。

1
2
3

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (mi) (map (lambda (ni) (dot-product ni mi)) cols) m)))

`(dot-product v w)`	returns the sum $\sum_{i} v_iw_i$
`(matrix-*-vector m v)`	returns the vector $t$, where $t_i = \sum_j m_{ij}v_j$
`(matrix-*-matrix m n)`	returns the matrix $p$, where $p_{ij} = \sum_{k} m_{ik}n_{kj}$
`(transpose m)`	returns the matrix $n$, where $n_{ij} = m_{ji}$