Matrices

A matrix in ATS is just a two-dimensional array but it is represented by a one-dimensional array and the representation is of the row-major style (in contrast to the column-major style). Given a type T, the type mtrxszref(T) is for a matrix combined with its number of rows and number of columns such that each element stored in the matrix is of the type T. I will loosely refer to values of the type mtrxszref(T) as matrices from now on. If there is a clear need to avoid potential confusion, I may also refer to them as matrix0-values.

Given a matrix M of dimension m by n, the expression M[i,j] means to fetch the content of the cell in M that is indexed by (i, j), where i and j are natural numbers strictly less than m and n, respectively. The expression M[i,j] can also be used as a left value. For instance, the assignment (M[i,j] := exp) means to evaluate exp to a value and then store the value into the cell in M that is indexed by (i, j).

Various functions and function templates on matrix0-values are declared in the file matrixref.sats, which is automatically loaded by atsopt. For instance, three function templates and two polymorphic functions on matrices are depicted by the following interfaces:

// fun{a:t@ype} mtrxszref_make_elt // template (row: size_t, col: size_t, x: a): mtrxszref (a) // fun mtrxszref_get_nrow{a:t@ype}(M: mtrxszref a): size_t // polyfun fun mtrxszref_get_ncol{a:t@ype}(M: mtrxszref a): size_t // polyfun // fun{a:t@ype} mtrxszref_get_elt_at // template (M: mtrxszref a, i: size_t, j: size_t): a // M[i,j] fun{a:t@ype} mtrxszref_set_elt_at // template (M: mtrxszref a, i: size_t, j: size_t, x: a): void // M[i,j] := x //

Given a type T and three values nrow, ncol and init of the types size_t, size_t and T, respectively, mtrxszref_make_elt<T> (row, col, init) returns a matrix of the type mtrxszref(T) such that the dimension of the matrix is nrow by ncol and each cell in the matrix is initialized with the value init. Given a matrix M of the type mtrxszref(T) for some T, mtrxszref_get_nrow(M) and mtrxszref_get_ncol(M) return the number of rows and the number of columns of M, respectively, which are both of the type size_t. For convenience, mtrxszref_get_nrow(M) and mtrxszref_get_ncol(M) can also be written as M.nrow and M.ncol, respectively. As for matrix access and update, the function templates mtrxszref_get_elt_at and mtrxszref_set_elt_at can be called, respectively. For convenience, bracket notation can used for these functions.

Let us now take a look at an example. The following defined function mtrxszref_transpose turns a given matrix into its transpose:

fun{a:t@ype} mtrxszref_transpose (M: mtrxszref a): void = let // val nrow = mtrxszref_get_nrow(M) // fnx loop1 (i: size_t): void = if i < nrow then loop2(i, 0) else () // and loop2 (i: size_t, j: size_t): void = if j < i then let val tmp = M[i,j] in M[i,j] := M[j,i]; M[j,i] := tmp; loop2(i, j+1) end else loop1(i+1) // end of [if] // in loop1 (0) end // end of [mtrxszref_transpose]

The matrix M is assumed to be a square, that is, its number of rows equals its number of columns. Note that the two functions loop1 and loop2 are defined mutually tail-recursively, and the keyword fnx indicates the need to combine the bodies of loop1 and loop2 so that mutual recursive tail-calls in these function bodies can be compiled into direct local jumps.