Умножьте две матрицы в SML

Question

Я хочу написать функцию в SML / NJ, которая будет принимать 2 матрицы в качестве аргументов и умножать их.

Я могу использовать только:

• функция точка, которая берет 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

Я не получаю ошибок, если в последней строке функции умножить я пишу 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))

Я не знаю, что еще мне делать. Кто-нибудь может мне помочь? 1039 *

Answer 1

Существует решение для OCaml на RosettaCode , которое вы можете перевести.

Учитывая иллюстрацию,

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

, затем для каждой строки в первой матрице рассчитайте произведение dot с тем же номером столбец второй матрицы. То есть w = dot ([1, 2], [a, b]). Извлечь строки первой матрицы легко, поскольку вы можете использовать рекурсию списка.

Извлечение столбцов второй матрицы менее просто, поскольку они ортогональны представлению списка (т. Е. a - первый элемент первой строки, b - первый элемент второй строки, c - это второй элемент первого ряда, а d - второй элемент второго ряда.

Вы можете упростить извлечение столбцов из второй матрицы, выполнив transpose, и в этом случае извлечение столбцов становится эквивалентным извлечению строк. В этот момент вы можете взять попарно dot произведение «строк» ​​(то есть строк в первой матрице и транспонированных столбцов («строк») во второй матрице).

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