Умножение матриц в схеме, список списков

Я начал изучать Схему и не понимаю некоторых из них. Я использую DrRacket.

Я написал следующий код:

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

Который использует эти функции:

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

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

В mult_matЯ умножаю матрицу A в каждом векторе транспонированной матрицы B. Это прекрасно работает.

Я нашел код в сети, который делает умножение таким образом, что я не понимаю:

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

В этом коде row это список списков матрицы А, но я не понимаю, как column Обновления.

Эта часть кода: (apply + (map * row column)) является точечным произведением вектора row и вектор column

Например: A - это матрица 2X3, а B - это матрица 3X2, и если вместо (apply + (map * row column)) я пишу 1тогда я получу матрицу 2X2 со значениями записей 1

Я не понимаю, как это работает.

Благодарю.

Источник

3 ответа

Решение

Ах, старый ( apply map foo _a_list_ ) трюк. Очень умно.

по факту (apply map (cons list A)) такой же как (apply map list A), Вот только как apply определяется для работы.

Испытание некоторых конкретных примеров обычно помогает "получить это":

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

Матричное перемещение. (список списков, правда.)

Так что у тебя есть

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

Обратите внимание это (λ B_column ...без скобок. В ((λ args ...) x y z)когда лямбда введена, args получает все аргументы, упакованные в список:

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

Также обратите внимание

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

следует той же "хитрой" схеме. Это на самом деле так же, как

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

по определению map,

Таким образом, применяя mapматрица "открывается" в список своих строк, а затем, когда 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.

Источник

Это решение может быть не лучшим способом его написания, но его легко понять:

      (define (matrixMultiply matrix1 matrix2)
    (define matrix2Transpose (matrixTranspose matrix2) ) ; Calculate matrix2 transpose to prevent recalculation in future
    (map 
        (lambda (row) ; Step1. Iterate through matrix1 rows
            (map
                (lambda (column) ; Step3. Iterate through matrix2 columns
                    (apply + (map * row column)) ; Step4. Multiply rows and columns by peer to peer and add them
                    ; Example: 
                    ; If row be (1 2) and column be (5 7) then:
                    ; Map part does: ((1 * 5) (2 * 7)) -> (5 14)
                    ; Apply part does: 5 + 14 -> 19
                )
                matrix2Transpose ; Step2. Use matrix2 transpose to get columns for every iteration
            )
        )
        matrix1
    )
)

(define (matrixTranspose matrix)
    (apply map (lambda _ _) matrix)
)

(display 
    (matrixMultiply '((1 2) (3 4)) '((5 6) (7 8)) )
)

Выход: ((19 22) (43 50))

Источник

Если вы предпочитаете использовать циклы while (что может быть проще для новичков), я рекомендую разделить проблему на 7 основных вспомогательных функций (наряду с некоторыми другими простыми функциями):

Это не самый эффективный метод (безусловно), но его легко понять.

  1. getRow mat i: получает строку i матрицы mat (список списков)

     (define (getRow mat i)
    (nthElement mat i))

    (define (nthElement lisT n)
    (if (= n 0)
        (car lisT)                                                 
        (nthElement (cdr lisT) (- n 1))))

  2. getCol mat i: получает столбец i матрицы mat (список списков)

    (define (getCol mat i)
    (define col (list))
    (define row 0)
    (while (< row (length mat))
        (set! col (append col (list (valueAtIJ mat row i))))
        (set! row (+ row 1)))
     col)

    (define (valueAtIJ mat i j)
    (nthElement (nthElement mat i) j))

  3. listMult list1 list2: выполняет поэлементное умножение двух списков

    (define (listMult list1 list2)
    (if (not (null? list1))
        (cons (* (car list1) (car list2)) (listMult (cdr list1) (cdr list2)))
        null))

  4. sum aList: вычисляет сумму всех элементов в списке

    (define (sum aList)
    (if (null? aList)
        0
        (+ (car aList) (sum (cdr aList)))))

  5. length aList: Находит длину списка

    (define (length lisT)
    (if (null? lisT)                                               
        0
        (+ 1 (length (cdr lisT)))))

  6. newMatrix m n val: создать матрицу размером m на n, заполненную значением val.

    (define (newMatrix m n val)                        
    (define i 0)
    (define row (list val))
    (define mat (list))
    (if (= n 0)
        (list)                                          
        (begin 
            (while (< i (- n 1))
                (set! row (append row (list val))) 
                (set! i (+ i 1)))
            (set! i 0)
            (while (< i m)
                (set! mat (append mat (list row)))     
                (set! i (+ i 1)))
    mat)))

  7. setValueAtIJ mat i j val: установить значение val в позиции i,j в mat (на основе 0)

    (define (setValueAtIJ mat i j val)
    (set! mat (setNthElementFinal mat i (setNthElementFinal (nthElement mat i) j val)))
    mat)

Все это можно комбинировать для создания функции умножения матриц. 

(define (matrixMult mat1 mat2)
    (define mat1Dim (list (length mat1) (length (nthElement mat1 0))))      
    (define mat2Dim (list (length mat2) (length (nthElement mat2 0))))      
    (define i 0)
    (define j 0)
    (define newMat (newMatrix (car mat1Dim) (car (cdr mat2Dim)) 0))        
    (if (not (= (car (cdr mat1Dim)) (car mat2Dim)))
        null                                                                
        (begin
            (while (< i (length newMat))
                (while (< j (length (nthElement newMat 0)))
                    (set! newMat (setValueAtIJ newMat i j (sum (listMult (getRow mat1 i) (getCol mat2 j)))))
                    (set! j (+ j 1)))
                (set! j 0)
                (set! i (+ i 1)))
        newMat)))
Источник
Другие вопросы по тегам