Матричное умножение ряда строк рекурсивно

Question

Я программирую свой собственный матричный модуль для развлечения и практики (сложность времени и пространства не имеет значения). Теперь я хочу реализовать умножение матриц, и я борюсь с этим. Это, вероятно, причина, по которой я использую Haskell, и у меня не было большого опыта с этим. Это мой тип данных:

data Matrix a =
M {
  rows::Int,
  cols::Int,
  values::[a]
}

Который хранит матрицу 3x2 как это в массиве:

1 2
3 4
5 6
= [1,2,3,4,5,6]

У меня есть несколько работающая функция транспонирования

transpose::(Matrix a)->(Matrix a)
transpose (M rows cols values) = M cols rows (aux values 0 0 [])
  where
   aux::[a]->Int->Int->[a]->[a]
   aux values row col transposed 
     | cols > col =
       if rows > row then 
         aux values (row+1) col (transposed ++ [valueAtIndex (M rows cols values) (row,col)])
       else aux values 0 (col+1) transposed
     | otherwise = transposed

Для индексации элементов в массиве я использую эту функцию

valueAtIndex::(Matrix a)->(Int, Int)->a
valueAtIndex (M rows cols values) (row, col) 
  | rows <= row || cols <= col = error "indices too large for given Matrix"
  | otherwise = values !! (cols * row + col)

Насколько я понимаю, я должен получить такие элементы для m1: 2x3 и m2: 3x2

m1(0,0)*m2(0,0)+m1(0,1)*m2(0,1)+m1(0,2)*m2(0,2)
m1(0,0)*m2(1,0)+m1(0,1)*m2(1,1)+m1(0,2)*m2(1,2)
m1(1,0)*m2(0,0)+m1(1,1)*m2(0,1)+m1(1,2)*m2(0,2)
m1(1,0)*m2(1,0)+m1(1,1)*m2(1,1)+m1(1,2)*m2(2,2)

Теперь мне нужна функция, которая принимает две матрицы, с rows m1 == cols m2 а потом как-то рекурсивно вычислить правильную матрицу.

multiplyMatrix::Num a=>(Matrix a)->(Matrix a)->(Matrix a)

Answer 1

Прежде всего, я не совсем уверен, что такой линейный список - хорошая идея. Список в Haskell моделируется как связанный список. Это означает, что, как правило, доступ к k- му элементу будет выполняться в O (k). Таким образом, для матрицы m×n это означает, что для доступа к последнему элементу требуется O(m n). Используя 2d связанный список: связанный список, который содержит связанные списки, мы уменьшаем его до O (m + n), что обычно быстрее. Да, есть некоторые издержки, так как вы используете больше конструкторов данных "против", но объем обхода обычно меньше. Если вам действительно нужен быстрый доступ, вы должны использовать массивы, векторы и т. Д. Но тогда есть и другие конструктивные решения, которые нужно принять.

Поэтому я предлагаю смоделировать матрицу как:

data Matrix a = M {
  rows :: Int,
  cols :: Int,
  values :: [[a]]
}

Теперь с помощью этого конструктора данных мы можем определить транспонирование как:

transpose' :: Matrix a -> Matrix a
transpose' (M r c as) = M c r (trans as)
    where trans [] = []
          trans xs = map head xs : trans (map tail xs)

(здесь мы предполагаем, что список списков всегда прямоугольный)

Так что теперь для умножения матриц. Если A и B являются двумя матрицами, а C = A × B, то это в основном означает, что a_{i, j} является точечным произведением i-й строки A и j-го столбца B. Или i-й ряд A и j-й ряд B^T (транспонирование B). Таким образом, мы можем определить скалярное произведение как:

dot_prod :: Num a => [a] -> [a] -> a
dot_prod xs ys = sum (zipWith (*) xs ys)

и теперь это только вопрос итерации по строкам и столбцам и помещения элементов в правильный список. Подобно:

mat_mul :: Num a => Matrix a -> Matrix a -> Matrix a
mat_mul (M r ca xss) m2 | ca /= ra = error "Invalid matrix shapes"
                        | otherwise = M r c (matmul xss)
    where (M c rb yss) = transpose m2
          matmul [] = []
          matmul (xs:xss) = generaterow yss xs : matmul xss
          generaterow [] _ = []
          generaterow (ys:yss) xs = dot_prod xs ys : generaterow yss xs