sml - 在 SML 中将两个矩阵相乘

Question

我想在 SML/NJ 中编写一个函数，它将 2 个矩阵作为参数，并将它们相乘。

我只能使用：

• 函数 dot，它采用 2 个向量并计算标量积：

  fun dot (xs: int list, ys: int list): int =
      List.foldl (fn (x,y) => x+y)
         0
         (ListPair.map (fn (x,y) => x*y) (xs, ys))
  

• 函数转置，它采用 1 个矩阵并计算该矩阵的转置：

  fun transpose (m: 'a list list): 'a list list =
      List.tabulate (List.length (List.nth (m, 0)),
             fn x => List.map (fn y => (List.nth (y, x))) m)
  

  • 匿名函数

  • 结构 List、ListPair 和 Math

我要写的函数应该是这样的：

fun multiply (a: int list list, b: int list list): int list list

到目前为止，我已经这样做了：

fun multiply (a: int list list, b: int list list): int list list =
case a of
[] => []
  | g::rep => [(List.map (fn y => dot(g, y)) transpose(b))] @ (multiply(rep, b))

但我得到了这个错误：

test.sml:66.21-66.62 Error: operator and operand do not agree [tycon mismatch]
  operator domain: int list list
  operand:         'Z list list -> 'Z list list
  in expression:
(List.map (fn y => dot <exp>)) transpose

如果在函数 multiply 的最后一行中我写的是 b 而不是 tranpose(b)，我没有收到任何错误，但是当然，如​​果我这样做，我不会得到我想要的结果：

fun multiply (a: int list list, b: int list list): int list list =
case a of
[] => []
  | g::rep => [(List.map (fn y => dot(g, y)) b)] @ (multiply(rep, b))

我不知道我还能做什么。任何人都可以帮助我吗？

标签： smlsmlnj

Answer 1

RosettaCode 上有一个 OCaml 解决方案，您可以翻译。

鉴于插图，

         | [ a,   [ c,
         |   b ]    d ]
---------+-------------
[ 1, 2 ] |   w      x
[ 3, 4 ] |   y      z

然后对于第一个矩阵中的每一行，计算与第二个矩阵dot的相同列数的乘积。即w = dot ([1, 2], [a, b])。提取第一个矩阵的行很容易，因为您可以使用列表递归。

提取第二个矩阵的列不太容易，因为它们与列表表示正交（即a是第一行b的第一个元素，是第二行的第一个元素，是第一行c的第二个元素，并且d是第二行的第二个元素。

您可以通过执行 a 来简化从第二个矩阵transpose中提取列的过程，在这种情况下，提取列等同于提取行。此时，您可以取dot“行”（即第一个矩阵中的行和第二个矩阵中的转置列（“行”））的成对乘积。

我鼓励使用Array2这种类型的操作，因为当您的“矩阵”（列表）呈锯齿状（具有不同的行长）时，您还可以避免错误处理。