SICP

Exercise 2.37. Suppose we represent vectors v = (vi) as sequences of numbers, and matrices m = (mij) as sequences of vectors (the rows of the matrix). For example, the matrix

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:

We can define the dot product as17

(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)))

矩阵操作回顾

这里可以回顾一下矩阵的几个操作。

dot product

dot product 只作用在两个向量之间

$$\left(a_1, a_2, \dots, a_n\right) \cdot \left(b_1, b_2, \dots, b_n\right) = a_1b_1 + a_2b_2 + \dots + a_nb_n $$

矩阵*向量

矩阵是 N 行 M 列矩阵，则该向量必须是一个 M 维的向量（M 列向量）。

$$\left[\begin{matrix} a & b \\ c & d \end{matrix} \right] \left(x, y\right) \mbox{=} \left(ax+by, cx+dy \right) $$ 注意，向量 * 矩阵（向量左乘矩阵），我们应当使用矩阵 * 矩阵来操作。

$$\left(x, y\right) \left[\begin{matrix} a & b \\ c & d \end{matrix} \right] \mbox{=} \left(ax+cy, bx+dy \right) $$

矩阵*矩阵

矩阵 A 是 N 行 M 列，矩阵 B 必须是 M 行，列数任意。

$$\left[\begin{matrix} a & b \\ c & d \end{matrix} \right] \left[\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix} \right] \mbox{=} \left[\begin{matrix}a+3b & 2a+4b \\ c+3d & 2c+4d \end{matrix} \right] $$

矩阵转置

只需要 (i, j) 位置的变为 (j, i) 位置就可以。

$$\left[\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}\right] \rightarrow \left[\begin{matrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{matrix}\right] $$

程序

matrix-*-vector

这个过程即对 matrix 中的每一行和 vector 进行点乘

(define (matrix-*-vector m v)
  (map (lambda (row)
         (dot-product row v))
       m))

transpose

使用 accumulate-n 即可以对每一行的第 n 个数进行一组操作，所以可以如下写：

(load "36-accumulate-n.scm")
(define (transpose mat)
  (accumulate-n cons '() mat))

matrix-*-matrix

我们可以对后面一个矩阵作一次转置，然后使用 map 对第一个矩阵与转置之后的第二个矩阵进行每一行点乘。

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (m-row)
           (map (lambda (n-col)
                  (dot-product m-row n-col))
                cols))
         m)))

测试

(load "../testframe.scm")
(assertequal? (dot-product '(1 2 3) '(4 5 6))
              (+ 4 10 18))
(assertequal? (transpose '((1 2 3) (4 5 6) (7 8 9)))
              '((1 4 7) (2 5 8) (3 6 9)))
(assertequal? (matrix-*-vector '((1 2 3)
                                 (4 5 6))
                               '(7 8 9))
              '(50 122))
(assertequal? (matrix-*-matrix '((1 2)
                                 (3 4)
                                 (5 6))
                               '((7 9)
                                 (8 10)))
              '((23 29)
                (53 67)
                (83 105)))

SICP 全笔记