Exercise 2.37 of SICP

2009-08-22

sicp

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

$$ M = \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_i w_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 as:

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

Solutions:

(define (accumulate fn init-value items)
  (if (null? items)
    init-value
    (fn (car items)
        (accumulate fn init-value (cdr items)))))

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

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

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

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

> (define n (list (list 1 2) (list 3 4)))
> (matrix-*-vector n (list 10 20))

(50 110)

> (transpose n)

((1 3) (2 4))

> (define m (list (list 1 2 3) (list 4 5 6) (list 7 8 9)))
> (matrix-*-matrix m m)

((30 36 42) (66 81 96) (102 126 150))

> (define q (list (list 9 1) (list 3 4) (list 6 7) (list 1 8)))
> (matrix-*-matrix (list (list 1 2 3 4) (list 5 6 7 8)) q)

((37 62) (113 142a))

Contents