Transpose matrix in prolog

Question

I want to transpose a matrix in prolog, so for example [[1,2,3],[1,2,3],[1,2,3]] should become [[1,1,1],[2,2,2],[3,3,3]]

Here is what I've done:

%transpose(M,T)
transpose([],[]).
transpose(M,[H|T]):-row(H,M,M1),transpose(M1,T).

%row(H, M, M1).
row([],[],[]).
row([H|Tt] , [[H|T1]|T] , [T1|Z]) :- row(Tt,T,Z).

Where M is to be transposed in T. Row predicate (not sure for the difference between predicate and function) get the head of each sublist in M, so I can get the entire first row of the new, transposed matrix T. I tested row separately, and it is giving the proper result. But when I try to transpose, I get only 'false' and nothing happens, no info for the new matrix T is printed.

Can anyone help me? Is the problem in the way I built the program? Or the result I expect is only true/false indeed and if so, how to get the new matrix? Thanks :)

A *function* does stuff. A *predicate* defines a relation. Prolog has *predicates* not *functions*. Did you try a `trace`? Try it with a simple example, like a 2x2 matrix and you'll see what happens. — lurker, Mar 28 '17 at 20:05
Q1: If I have a sorting algorithm, it does stuff, why shouldn't I call it a function? Q2: Can you take a look at the transposing? :) — Petar D., Mar 28 '17 at 20:08
You think of it as "doing stuff" but in Prolog it means that one list is related to the other in that it is a sorted version of that list. The relation implies that it could also go in reverse: the first list is an *unsorted* version of the second. Functions don't behave that way. Relations do. That said, yes, there are some Prolog predicates (like `sort`) that do behave functionally. But others do, like `append/3` and `reverse/2`, etc. If you had a "function" `reverse(A, B)` you wouldn't get a result if you called `reverse(A, [1,2,3])` but in Prolog you will. — lurker, Mar 28 '17 at 20:10
Try the `trace` like I suggested. You'll see what's happening. — lurker, Mar 28 '17 at 20:11
I can't find a proper guide how to trace in `SWI-Prolog`. I did open the program, clicked on `transpose/2` and clicked trace, then tried to start it the usual way, but still I get only `false` and nothing is being traced. — Petar D., Mar 28 '17 at 20:17
I usually use it on the command line. It's a "state" you put Prolog in. You want to be in "trace mode". On the command line, one would just enter `trace.` Then enter your query. Press return for each prompt to go to the next step. What's happening is that your `transpose` is recursing down to `[[], [], []]` not `[]`. So the base case fails. — lurker, Mar 28 '17 at 20:26
I did this: base case: `transpose( [ [ ] | _ ] ,[ ] ).` but I'd like if you suggest something smarter, as this doesn't look good to me. — Petar D., Mar 28 '17 at 20:44
[Here is implementation](https://github.com/SWI-Prolog/swipl-devel/blob/41b639d5aed3a7f370051885d21138932e83fcf7/library/clp/clpfd.pl#L6848-L6858) which looks easy enough to read if you understand fold and map. It is also linked in [here](http://stackoverflow.com/a/4281159/7473772). Did you see this question when you wrote your question? How is it different? — , Mar 29 '17 at 10:52
Possible duplicate of [How to transpose a matrix in prolog](http://stackoverflow.com/questions/4280986/how-to-transpose-a-matrix-in-prolog) — , Mar 29 '17 at 10:56

score 2 · Answer 1 · edited Jul 24 '19 at 16:16

First, a note on terminology: One characteristic of a function is that each input is related to exactly one output. On the other hand, a relation can hold for multiple such combinations. Prolog predicates induce relations between their arguments, and multiple answers can arise on backtracking.

As to your concrete question, @lurker has already given some solid advice.

However, as you already notice, tracing quickly gets very complex in Prolog, and I would therefore like to complement what lurker has written by explaining a few principles of declarative debugging in Prolog.

In essence, we will aim to make our problem simpler instead of harder. We start with the case you mention for the program you posted:

?- transpose([[1,2,3],[1,2,3],[1,2,3]], Ls).
false.

In logical terms, the relation is too specific: It fails to hold in a case in which it ought to hold.

To find a reason for this problem, we could step through the precise execution details, using a textual or graphical tracer, and try to keep track of all the details. This is extremely hard, so I suggest you first try to find a simpler case that still fails.

I will do this by generalizing the query. There are several ways to do this. For example, instead of concrete integers, I can use fresh variables:

?- transpose([[_,_,_],[_,_,_],[_,_,_]], Ls).
false.

Aha, so we have found a much more general case that still fails. As long as this case fails, the more specific case will definitely also fails, because we are reasoning over a pure and monotonic logic program.

So, the new question is: Why does this more general query fail? To find a reason, we can simply further generalize the query. For example, instead of reasoning about lists with 3 elements each, we can generalize this to the following case, where two of the lists are generalized to "more than one element":

?- transpose([[_|_],[_|_],[_,_,_]], Ls).
false.

We see that this much more general query still fails. We can even generalize it further:

?- transpose([_,_,[_,_,_]], Ls).
false.

This still fails! Note that we can also take it too far. For example:

?- transpose([_,_,_], Ls).
nontermination

Here, we run into a different issue altogether, related to termination properties of the program. However, in our case, we want to find a reason for the unexpected failure, and so we return to the case above:

?- transpose([_,_,[_,_,_]], Ls).
false.

At this point, there is not much more to generalize, so we could now invoke the tracer on this simplified query.

However, we can also continue in a different direction: Not every test case needs to be a generalization. We can also come up with an entirely different case, such as a list with only two (instead of three) elements:

?- transpose([_,[_,_,_]], Ls).
false

Aha, so this also fails, even though it ought to succeed!

What about even simpler cases:

?- transpose([[_,_,_]], Ls).
false.

And further:

?- transpose([[_,_]], Ls).
false.

And even further:

?- transpose([[_]], Ls).
false.

Each of these queries ought to succeed, but fails.

Why?

To find reasons, consider program-slicing of the underlying logic program. For example, let us take one of the simplest queries we found that should succeed, but doesn't: ?- transpose([[_]], _).

I use the following definition to generalize away constraints (= goals) of the original program

:- op(950,fy, *).
*_.

For example, we can generalize row/3 as follows:

row([], [], []).
row([H|Tt], [[H|T1]|T], [T1|Z]) :-
        * row(Tt,T,Z).

Even with this much more general version of row/3, we get:

?- transpose([[_]], Ls).
false.

This means: To make this query succeed, you either have to add additional clauses to your code (to make it more general) or change the remaining fragment.

Like lurker, I also leave the rest as an exercise.

"One characteristic of a function is that each input is related to exactly one output" -- the quadratic equation will be ashamed to discover that it is no longer a funcktion . ~~kintalken~~ — Kintalken, Mar 31 '17 at 06:08
If it only finds this out now, there are other things to be ashamed of too! — mat, Mar 31 '17 at 06:13
it's a good idea . let's just pretend that __in computer programming__ , a **function** only provides one answer to the solution , but a **procedure** provides 0 or 1 or many answers to the solution . Note that by "procedure" here I mean exactly what a prolog programmer knows as a funcktor . By "function" here I mean exactly what a prolog programmer knows as "a funcktor to which was automatically added a 1st arg return value named "shift" and for which the body has been wrapped in a call to "once" .. contd : — Kintalken, Apr 07 '17 at 08:15
A **function** has 0 or 1 (explicit) return values . It accepts returns arguments by-value . A **procedure** has 0 or 1 or more (explicit) return values , it accepts and returns arguments by-reference . A **function** can only supply a fully instantiated return value . "fully instantiated" means that it contains no variables . A **procedure** can supply a fully or a partially instantiated return value . "partially instantiated" means that it does contain variables .. contd : — Kintalken, Apr 07 '17 at 08:16
A **function** uses the "return value" for it's own purposes , thus it has an (explicit) return value but it does NOT have an (implicit) return value . A **function** thus always returns false (yes false , thx YieldProlog) because it cannot evluate conditions such that it is enabled to make a statement of "true".. contd : — Kintalken, Apr 07 '17 at 08:18
A **procedure** does not use the "return value" for it's own purposes , thus it has many (explicit) return values passed by-reference through it';s arguments , but ALSO an (implicit) return value which if "false" means "these considerations cannot provide a valid answer" and if "true" means "these considerations are providing a valid answer" :end..~~kintalken~~ — Kintalken, Apr 07 '17 at 08:19
i think this is a great way to describe the variables of prolog : variables in prolog are always passed by-reference . This is like the C++ example ```void whatever(int &foo) { foo = 2)``` . As in C++ , a change to a variables value from within the procudure is propogated out to the caller . Prolog has a further restriction compared to C++ . You are only allowed to set the value of a variable once . If you try to set a variable that has already been set then your procedure abandons the current answer and returns false . To set a variable to multple values , you must generate multiple answers — Kintalken, Apr 07 '17 at 08:28

lurker · Answer 2 · 2017-03-28T22:15:29.437

Prolog only has predicates not functions. A predicate defines a relation, and generally isn't thought of as "doing something" as much as it is "defining something. Your row/3 actually defines a relationship between its 3 arguments. The 3 arguments are related in that the elements of the 1st and 3rd lists are the heads and tails of the arguments of the 2nd list. I'll show 3 different queries that illustrate:

| ?- row([a,b,c], L, M).

L = [[a|A],[b|B],[c|C]]
M = [A,B,C]

yes
| ?- row(A, [[a,b,c],[d,e,f],[g,h,i]], L).

A = [a,d,g]
L = [[b,c],[e,f],[h,i]] ? ;

no
| ?- row(A, B, [[a,b],[c,d],[e,f]]).

A = [C,D,E]
B = [[C,a,b],[D,c,d],[E,e,f]] ? ;

no
| ?-

A function would not behave this way. Also you can see that, knowing the relationship, the name is a bit generic. row doesn't really adequately describe the relationship. Perhaps it could be called heads_and_tails/3, and maybe swap the 1st and 2nd argument.

The reason your transpose/2 predicate is failing is that it recurses down to a list of empty lists ([[], [], []] in the case of a matrix with 3 rows), but your transpose/2 base case is based upon [].

Let's look at substituting, as suggested in the comment, the base case of transpose([], []) with:

transpose([[] | _], []).

The following example queries result:

| ?- transpose([[a,b,c],[d,e,f]], T).

T = [[a,d],[b,e],[c,f]] ? ;

no
| ?- transpose([[a,b,c],[d,e,f], [a]], T).

no
| ?- transpose(T, [[a,b,c],[d,e,f]]).

T = [[a,d],[b,e|_],[c,f|_]] ? ;

no

So incorrect results occur for the second query. One approach to resolve this, following along the logic of this predicate, is to change the base case from transpose([], []) to this:

transpose(Empty, []) :- maplist(=([]), Empty).

This results in a predicate that will give the following results:

| ?- transpose(T, [[a,b,c],[d,e,f]]).

T = [[a,d],[b,e],[c,f]] ? a

no
| ?- transpose([[a,b,c],[d,e,f]], T).

T = [[a,d],[b,e],[c,f]] ? a

no

score -1 · Answer 3 · edited May 31 '17 at 18:56

It turns out that the previous solution was inadequate because it was only a description of logical relationships.

What is required in addition to the specification of the relationships is an iteration of facts that are subsequently made subject to the relationships.

In the following program it is foreach that is used to generate the facts.

Tested on swipl.

Example queries follow the program.

    */

    (
        program(INPUT_VECTOR,OUTPUT_VECTOR)
    )
    :-
    (
        (
            (
                INPUT_TRUTH_GOAL
            )
            =
            (
                item(INPUT_VECTOR,J_INDEX,K_INDEX,ITEM)
            )
        )
        ,
        (
            (
                OUTPUT_TRUTH_GOAL
            )
            =
            (
                item(OUTPUT_VECTOR,K_INDEX,J_INDEX,ITEM)
            )
        )
        ,
        (
            (
                nonvar(INPUT_VECTOR)
            )
            *->
            (
                once(foreach(INPUT_TRUTH_GOAL,OUTPUT_TRUTH_GOAL))
            )
            ;
            (
                (
                    nonvar(OUTPUT_VECTOR)
                )
                *->
                (
                    once(foreach(OUTPUT_TRUTH_GOAL,INPUT_TRUTH_GOAL))
                )
            )
        )
    )
    .

    (
        item(VECTOR,J_INDEX,K_INDEX,ITEM)
    )
    :-
    (
        (
            nth1(J_INDEX,VECTOR,SUBVECTOR)
        )
        ,
        (
            nth1(K_INDEX,SUBVECTOR,ITEM)
        )
    )
    .

    /*

Testing:

Three test queries demonstrate that the program is basically fit:

    ?-
    program([[1,2,3],[4,5,6],[7,8,9]],[[1,4,7],[2,5,8],[3,6,9]])
    .
    true.

    ?-
    program([[1,2,3],[4,5,6],[7,8,9]],OUTPUT_VECTOR)
    .
    OUTPUT_VECTOR = [[1, 4, 7|_830], [2, 5, 8|_962], [3, 6, 9|_1100]|_356]  .

    ?-
    program(INPUT_VECTOR,[[1,4,7],[2,5,8],[3,6,9]])
    .
    INPUT_VECTOR = [[1, 2, 3|_560], [4, 5, 6|_626], [7, 8, 9|_698]|_350]    .

    ?-

Unfortunately the program fails a steadfast test:

    ?-
    program(INPUT_VECTOR,OUTPUT_VECTOR)
    ,
    INPUT_VECTOR = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    .

    false .

    ?-

Transpose matrix in prolog

3 Answers3

Why?