行主序的矩阵递归乘法

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)

现在我需要一个函数，它接受两个矩阵，其中 m1 的行数等于 m2 的列数，然后以某种递归的方式计算出正确的矩阵。

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

- janschill

---

说实话，我认为转置操作相当“不优雅”和“低效”（因为对于每个元素，您都要遍历列表才能访问该元素，并且还要将其附加到列表末尾，因此对于一个m x n矩阵，这可能会随着m^2 x n^2的规模逐渐增大。 - Willem Van Onsem

此外，我并不清楚您期望得到什么样的答案？完整的解决方案吗？那么这个任务的意义是什么？ - Willem Van Onsem

我不必使用转置。那只是一个帮助函数，让我更好地理解这个概念。 - janschill

这并不是一项作业，我需要的是如何更容易地解决这个问题的帮助。 - janschill

时间和空间复杂度并不重要 - 现在我感到很想设计一个O(n!)的矩阵乘法算法... - leftaroundabout

Answer 1

首先，我并不是很信服这种线性列表的好处。在Haskell中，列表采用链接列表模型。因此，通常访问第k个元素需要O(k)的时间复杂度。对于一个m×n矩阵来说，访问最后一个元素需要O(m n)的时间。通过使用二维链表：包含链表的链表，我们将时间复杂度缩小到O(m+n)，这通常更快。是的，虽然会有一些开销，因为你会使用更多的"cons"数据构造器，但遍历次数通常更少。如果您确实需要快速访问，则应使用数组、向量等数据结构。但是，还有其他设计决策需要考虑。

因此，我建议我们将矩阵建模为：

data Matrix a = M {
  rows :: Int,
  cols :: Int,
  values :: <b>[</b>[a]<b>]</b>
}

现在有了这个数据构造器，我们可以将转置定义为：

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}是A的第i行和B的第j列的点积。或者是A的第i行和B^T（即B的转置）的第j行的点积。因此，我们可以将点积定义为：

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

- Willem Van Onsem

---

另请参见Data.List.transpose。 - luqui