Multiply two matrices in SML

I want to write a function in SML/NJ which will take 2 matrices as an arguments and it will multiply them.

I can only use:

function dot, which take 2 vectors and calculate scalar product:

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

function transpose, which take 1 matrix and calculate transpose of this matrix:

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)

anonymous function
structures List, ListPair and Math

The function I want to write should be like this:

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

So far I have done this:

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

But I got this error:

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

I get no errors, if in the last line of function multiply I write b instead of tranpose(b), but of course, if I do this, I don't the the resoult I want:

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

I don't know what else should I do. Can anybody pease help me?

Solution

There exists a solution for OCaml on RosettaCode that you can translate.

Given the illustration,

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

then for each row in the first matrix, calculate the dot product with the same number column of the second matrix. I.e. w = dot ([1, 2], [a, b]). Extracting the rows of the first matrix is easy, since you can use list recursion.

Extracting the columns of the second matrix is less easy, because they are orthogonal to the list representation (i.e. a is the first element of the first row, b is the first element of the second row, c is the second element of the first row, and d is the second element of the second row.

You can simplify extracting columns from the second matrix by performing a transpose in which case extracting columns becomes equivalent to extracting rows. At this point you can take the pairwise dot product of "rows" (that is, rows in the first matrix and transposed columns ("rows") in the second matrix).

I would encourage the use of Array2 for this type of operations, since you also avoid error handling when your "matrices" (lists) are jagged (have different row lengths).