CODEWITHSUNDEEP
prolog
user2245846
user2245846

Reputation: 3

Transpose matrix of a square matrix explanation

I´ve got this code, prolog code. It´s purpose is to obtain the transpose matrix of a given square matrix. Can somebody explain to me what does this code do step by step?

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

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

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

Upvotes: 0

Views: 426

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

The key is really understanding lists_firsts_rests/3 and Boris's remark is spot on. Let's run it through trace:

?- trace.
[trace]  ?- lists_firsts_rests([[a,b,c],[d,e,f],[g,h,i]], X, Y).

   Call: (6) lists_firsts_rests([[a, b, c], [d, e, f], [g, h, i]], _G1914, _G1915) ? creep
   Call: (7) lists_firsts_rests([[d, e, f], [g, h, i]], _G2030, _G2033) ? creep
   Call: (8) lists_firsts_rests([[g, h, i]], _G2036, _G2039) ? creep
   Call: (9) lists_firsts_rests([], _G2042, _G2045) ? creep
   Exit: (9) lists_firsts_rests([], [], []) ? creep
   Exit: (8) lists_firsts_rests([[g, h, i]], [g], [[h, i]]) ? creep
   Exit: (7) lists_firsts_rests([[d, e, f], [g, h, i]], [d, g], [[e, f], [h, i]]) ? creep
   Exit: (6) lists_firsts_rests([[a, b, c], [d, e, f], [g, h, i]], [a, d, g], [[b, c], [e, f], [h, i]]) ? creep
X = [a, d, g],
Y = [[b, c], [e, f], [h, i]].

So you can see what's happening here is that lists_firsts_rests/3 is just peeling off the first item in each of the lists of the argument and returning them in their own list, and another list with all of the rests. The effect here is that when it saw [[a,b,c],[d,e,f],[g,h,i]], what it really saw was [[a|X],[d|Y],[g|Z]] and it returned two things, the list [a,d,g] and [X,Y,Z].

trans/3 is just a classic Prolog inductive loop. It's folding lists_firsts_rests/3 across the matrix. It should be clear how that would produce a transposed matrix, since in the trace it clearly converted 3x3 matrix into a vector of length 3 and a 2x3 matrix "remainder."

trans/2 is another classic Prolog pattern, this one setting up the recursion for trans/3 and starting the loop. A more classic naming policy here would be to call trans/2 transpose/2 and trans/3 transpose_loop/3, because that's really what they are.

Hope this helps.

Upvotes: 1

Related Questions