SICP 問題 2.37（ベクタ、マトリクスの演算）

【問題】

ベクタ v = (v_i) を数の並びで、マトリクス m = (m_ij) をベクタ（マトリクスの行）の並びで表現するとしよう。例えばマトリクス

┌ 1 2 3 4 ┐

│ 4 5 6 7 │

└ 6 7 8 9 ┘

は、並び

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

と表現する。この表現を使えば、並びの演算を使ってマトリクスやベクタの基本演算を簡潔に表すことができる。
これらの演算（大抵の行列演算の教科書に書いてある）は次の通り。

(dot-product v w)      総和 Σi v_i・w_i を返す。

(matrix-*-vector m v)  t_i = Σi m_ij・v_j であるようなベクタ t を返す。

(matrix-*-matrix m n)  p_ij = Σk m_ik・n_kj であるようなマトリクス p を返す。

(transpose m)          n_ij = m_ji であるようなマトリクス n を返す。

内積は

(define (dot-product v w)

  (accumulate + 0 (map * v w)))

と定義できる。他のマトリクス演算を計算する次の手続きの欠けた式を補え。
（手続き accumulate-n は問題 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 使えば終わりか。

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

では実験。

gosh> (define m '((1 2 3 4) (4 5 6 7) (6 7 8 9)))

m

gosh> m

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

gosh> (matrix-*-vector m '(1 2 3 4))

(30 60 80)

gosh> 

紙で検算してみたら正しく処理されているふう。

transpose

行と列を入れ替えたマトリックスを求める演算。（これは次の matrix-*-matrix で必要になると思う。）
入力マトリックスを変換したリストを新たな行として構成するにはどうするか、というコンセプトで考えればできそう。前問と同じパターンですな。

入力されるマトリクスを、((1 2 3 4) (4 5 6 7) (6 7 8 9) ) とする。
その場合、各リストの car を抽出してリストを作成すると、

１回目：先頭＝(1 4 6) ・・・残り部分＝ ((2 3 4) (5 6 7) (7 8 9) )

２回目：先頭＝(2 5 7) ・・・残り部分＝ ((3 4) (6 7) (8 9) )

３回目：先頭＝(3 6 8) ・・・残り部分＝ ((4) (7) (9) )

４回目：先頭＝(4 7 9) ・・・残り部分＝ (() () () )

ここまで書けば俺でも分かる。これを実現するには累積処理を行う手続きを cons で指定してやればいいだけ。

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

では実験。

gosh> (transpose '((7 8 9) (8 9 0) (9 0 1) (0 1 2)))

((7 8 9 0) (8 9 0 1) (9 0 1 2) )

gosh> 

よしよし。

matrix-*-matrix

マトリクス同士の積を求める演算。
問題文の歯抜け定義だと、map の中の処理だけ考えればいいふう。
matrix-*-vector 使えばよさげ。まぁ問題の流れから当然ちゃあ当然なわけだが。

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x)
	   (matrix-*-vector cols x))
	 m)))

(matrix-*-vector cols x) は一瞬左右の順序が逆になっていてダメな演算に見えるけど、実際に処理される内容を考えれば逆転しても問題ないことに気づく。
では実験。
見やすさのために m1 と n1 というマトリックスを定義しちゃって、それを演算する。

gosh> (define m1 '((1 2 3 4) (2 3 4 5) (3 4 5 6)))

m1

gosh> (define n1 '((7 8 9) (8 9 0) (9 0 1) (0 1 2)))

n1

gosh> (matrix-*-matrix m1 n1)

((50 30 20) (74 48 32) (98 66 44) )

こいつも紙で検算してみたら正しく処理されているふう。

というわけで以上、マトリクス演算に関する問題でした〜。