How to transpose a matrix in prolog

Here's a fragment of a larger answer:

% transposed(+A, ?B) iff matrix B is transposed matrix A
transposed(A, B) :- transposed(A, [], B).
transposed(M, X, X) :- empty(M), !.
transposed(M, A, X) :- columns(M, Hs, Ts), transposed(Ts, [Hs|A], X).

% empty(+A) iff A is empty list or a list of empty lists
empty([[]|A]) :- empty(A).
empty([]).

% columns(+M, ?Hs, ?Ts) iff Hs is the first column
%   of matrix M and Ts is the rest of matrix M
columns([[Rh|Rt]|Rs], [Rh|Hs], [Rt|Ts]) :- columns(Rs, Hs, Ts).
columns([[]], [], []).
columns([], [], []).

This is the smallest solution I could come up with.

Code

transpose([[]|_], []).
transpose(Matrix, [Row|Rows]) :- transpose_1st_col(Matrix, Row, RestMatrix),
                                 transpose(RestMatrix, Rows).
transpose_1st_col([], [], []).
transpose_1st_col([[H|T]|Rows], [H|Hs], [T|Ts]) :- transpose_1st_col(Rows, Hs, Ts).

Test

:- transpose([[1,2,3],
              [4,5,6],
              [7,8,9]], R),
   print(R).

Prints:

[[1,4,7],
 [2,5,8],
 [3,6,9]]

Explanation

The way it works is that transpose will recursively call transpose_1st_col which extracts and transposes the first column of the matrix. For example:

:- transpose_1st_col([[1,2,3],
                      [4,5,6],
                      [7,8,9]], Row, RestMatrix),
   print(Row),
   print(RestMatrix).

will print

[1,4,7]

and

[[2,3],
 [5,6],
 [8,9]]

This is repeated until the input matrix is empty, at which point all columns have been transposed. The transposed columns are then joined into the transposed matrix.

Not sure your example is correct, but I get the idea.

If using SWI-PROLOG, you can use the CLPFD module, like so:

:- use_module(library(clpfd)).

Allowing you to use the transpose/2 predicate, like this:

1 ?- transpose([[1,2,3],[4,5,6],[6,7,8]], X).
X = [[1, 4, 6], [2, 5, 7], [3, 6, 8]].

Otherwise (if no SWI-PROLOG), you could simply use this implementation (which happened to be an old one in SWI's clpfd):

transpose([], []).
transpose([F|Fs], Ts) :-
    transpose(F, [F|Fs], Ts).

transpose([], _, []).
transpose([_|Rs], Ms, [Ts|Tss]) :-
        lists_firsts_rests(Ms, Ts, Ms1),
        transpose(Rs, Ms1, Tss).

lists_firsts_rests([], [], []).
lists_firsts_rests([[F|Os]|Rest], [F|Fs], [Os|Oss]) :-
        lists_firsts_rests(Rest, Fs, Oss).

For an updated version which uses foldl and maplist built-ins, see clpfd.pl.