Matrix transposition is an important technique for many applications. If \[A=[a_{ij}]_{m\times n}\] then \[A^T=[a_{ij}]_{n\times m}\] in mathematical terms, but what does function \(A^T\) look like when implementation functionally?
Matrices are rows of columns, \(a_{12}\) addresses row \(1\), column \(2\). The first index identifies the row, the second identifies the column. ‘Same-length row vectors’ is another way to think of a matrix.
Note that a ‘column vector’ is a \(m\times1\) matrix. Modelled functionally as a list, exemplar [[1], [2], [3]] defines a \(3\times1\) matrix, or a 3-row column vector; rows all have dimension of 1, meaning all sub-lists have length of 1.
One matrix therefore comprises zero or more row vectors of equal dimension. The nil matrix matches the nil vector, an empty list.
Row or Column Major
Storage order does not matter in a functional context.
Assuming that a two-dimensional matrix is a list of lists, what do you call a row and a column? Take an example, [[a, b, c], [d, e, f]] is a list of two lists each of three cells. Is it a 2-row 3-column matrix or a 3-row 2-column matrix? Is row the major axis with column as minor, or the other way around? The answer determines how you address the cells. Cell \(a_{12}=b\) for row-major addressing but \(a_{12}=d\) for column major. In the first case, the sub-lists arrange horizontally where \(a_{12}\) identifies row 1, column 2. In the second case, sub-lists arrange vertically.
Going forward, ‘row’ hereafter refers to the sub-lists of equal length belonging to a matrix list. The first ‘scalar’ from all the rows constitutes the first column. Scalar here just refers to the contents \(a_{ij}\) of matrix \(A\), type of value arbitrary.
Degenerate Correctly, Address Non-Deterministically
Correct degeneration for no rows or columns is a requirement. Correct addressing of cells is another.
The predicate below is mode (?, ?, +, ?) meaning that you can find matches for unknown Row, Column or Scalar. You can use this to find specific Scalar values; or else find the Scalar value for some Row or some Row and Column specifically; and so on. Prolog finds all the matching solutions.
matrix_nth1(Row, Column, Matrix, Scalar) :-
nth1(Row, Matrix, Vector),
nth1(Column, Vector, Scalar).Argument ordering reflects \(a_{ij}\), row \(i\) and column \(j\).
Transpose in Prolog
A grandfather of functional languages, Prolog, lets you express the matrix transpose relationship in a pure form. It can lay the foundation for Erlang, or any other functional implementation.
matrix_transpose(A, []) :-
maplist(=([]), A),
!.
matrix_transpose(A, [V0|V]) :-
maplist([[H|T], H, T]>>true, A, V0, A_),
matrix_transpose(A_, V).In this predicate implementation, V stands for vector; V0 is the outgoing head vector. A matrix is zero or more vectors of equal dimension. ‘Equal dimension’ means equal list-length since a vector is a list in this context.
The transpose only succeeds if the final list of vectors unify with nil, or [] in Prolog terms. See the first clause. Mapping the final row with goal =([]) unifies each terminating sub-row with nil else fails. Put another way, the row lengths must match for successful transposition.
Transpose in Erlang
The naive direct translation to Erlang pans out as follows.
-module(matrix).
-export([transpose/1]).
-type t() :: [] | [[any()]].
-spec transpose(T :: t()) -> t().
transpose(T) ->
case lists:all(fun(X) -> X == [] end, T) of
true ->
[];
false ->
[lists:map(fun hd/1, T) | transpose(lists:map(fun tl/1, T))]
end.Notice that recursion only terminates if all the incoming row-tails match the empty list, [], and not just the first row.
List Comprehensions in Erlang
Transpose by comprehension offers an alternative approach.
transpose([[] | _]) -> [];
transpose([[Head | Tail] | Lists]) ->
[[Head | [H || [H | _T] <- Lists]] | transpose([Tail | [T || [_H | T] <- Lists]])].List comprehensions act as filters therefore do not correctly error when the matrix row-vectors mismatch. Filter is not the correct behaviour when row length mismatch. Erlang should raise an error not filter out unexpected patterns.
Hence the following holds true for the comprehension approach. It succeeds but should strictly-speaking fail with error because the incoming list is not a matrix.
[[1, a, b], [2], [3]] == transpose([[1, 2, 3], [a], [b]]).Results
Add it all together. Requirements summarise:
- Transpose arbitrary lists of same-length lists.
- Succeed for nil lists.
- Fail correctly for non-conforming nested lists; those that fail the same-length assumption.
After some fiddling:
%% @type rows(). The type does <em>not</em> include the empty matrix, identical
%% to an empty list; a matrix must possess at least one row and one column.
-type rows() :: [[any()]].
%% @doc Transposes matrix.
%%
%% Recursion ends when all the rows `H' of matrix `T' match the empty list `[]'
%% and this cannot appear as a guard condition because standard library {@link
%% lists:all/2} cannot execute within a guard.
%%
%% Two sub-functions (prime and prime-prime where underscore stands for prime
%% within the code) help to correctly match against `[]' and terminating tails,
%% e.g. `[[], [], []]', which should fail with error if presented initially to
%% {@link transpose/1} but successfully terminate for mapped row-vector tails.
-spec transpose(Rows :: [] | rows()) -> [] | rows().
transpose([]) -> [];
transpose(Rows) -> transpose_(Rows).
transpose_(Rows) -> [lists:map(fun hd/1, Rows) | transpose__(lists:map(fun tl/1, Rows))].
transpose__(Rows) ->
case lists:all(fun(Row) -> Row == [] end, Rows) of
true -> [];
false -> transpose_(Rows)
end.Matrix transposition!