Matrix multiplication in scheme, List of lists

Question

I started to study Scheme and I do not understand some of it. I'm using DrRacket.

I wrote the following code:

(define mult_mat
  (λ (A B)
    (Trans_Mat (map (λ (x) (mul_Mat_vec A x))
                    (Trans_Mat B)))))

That uses this functions:

(define Trans_Mat
  (λ (A)
    (apply map (cons list A))))

---

(define mul_Mat_vec
  (λ (A v)
    (map (λ (x) (apply + (map * x v)))
         A)))

In mult_mat, I multiply the matrix A in each vector of the transpose matrix B. It works fine.

I found a code on the web that makes the multiplication in a way that I don't understand:

(define (matrix-multiply matrix1 matrix2)
  (map
   (λ (row)
     (apply map
       (λ column
         (apply + (map * row column)))
       matrix2))
   matrix1))

In this code, row is a list of the lists of matrix A, but I don't understand how the column updates.

This part of the code: (apply + (map * row column)) is the dot product of vector row and vector column

For example: A is a matrix 2X3 and B is a matrix 3X2 and if instead of (apply + (map * row column)) I write 1, then I'll get a matrix 2X2 with entries valued 1

I don't understand how it works.

Thanks.

Answer 1

Ah, the old ( apply map foo _a_list_ ) trick. Very clever.

In fact (apply map (cons list A)) is the same as (apply map list A). That's just how apply is defined to work.

Trying out some concrete examples usually helps to "get it":

(apply map       list '((1 2 3)  (10 20 30)) )
=
(apply map (cons list '((1 2 3)  (10 20 30))))
=
(apply map (list list  '(1 2 3) '(10 20 30) ))
=
(      map       list  '(1 2 3) '(10 20 30)  )
=
'((1 10) (2 20) (3 30))

Matrix transposition. (list of lists, really.)

So you have

(define (mult_mat A B)
    (Trans_Mat (map (λ (B_column) (mul_Mat_vec A B_column))
                    (Trans_Mat B))))

(define (Trans_Mat A)
    (apply map list A))

(define (mul_Mat_vec A v)
    (map (λ (A_row) (apply + (map * A_row v)))
         A))

(define (matrix-multiply A B)
  (map
    (λ (A_row)
      (apply map
             (λ B_column
               (apply + (map * A_row B_column)))
             B))
    A))

Notice it's (λ B_column ..., without parentheses. In ((λ args ...) x y z), when the lambda is entered, args gets all the arguments packaged in a list:

((λ args ...) x y z)
=
(let ([args (list x y z)])
  ...)

Also notice

      (apply map
             (λ B_column
               (apply + (map * A_row B_column)))
             B)

follows the same "tricky" pattern. It's in fact the same as

      (apply map (cons
             (λ B_column
               (apply + (map * A_row B_column)))
             B    ) )
=
      (      map
             (λ B_column
                (apply + (map * A_row B_column)))
             B_row1
             B_row2
             ....
             B_rowN )
=
     (cons (let ([B_column_1 (map car B)])
                (apply + (map * A_row B_column_1)))
           (map (λ B_column
                    (apply + (map * A_row B_column)))
             (map cdr B_row1)
             (map cdr B_row2)
             ....
             (map cdr B_rowN) )
=
     (cons 
       (apply (λ B_column (apply + (map * A_row B_column)))
              (map car B))
       (apply map
              (λ B_column
                 (apply + (map * A_row B_column)))
              (map cdr B)))

by the definition of map.

Thus, by applying the map, the matrix is "opened up" into the list of its rows, and then when map gets to work on these rows as its arguments, the lambda function gets applied to each row's subsequent numbers, in unison, correspondingly; thus achieving the same effect as the explicit transposition had. But now the added bonus is, we don't need to transpose the result back into the proper form, as we have to do with your first version.

This is very clever, and nice.