Prolog indirect relationship

Question

I'm just start learning Prolog and facing a wired problem:

Suppose I have people waiting in two lines:

left(a,b).
left(c,i).
left(i,j).
right(k,j).

which represents lines like these:

line1:a,b  line2: c,i,j,k.

What I want is to see if any of these people are in same line. What I've wrote is following rules:

nextto(X,Y):- left(X,Y);left(Y,X);right(X,Y);right(Y,X).
sameline(X,Y):- nextto(X,Y).
sameline(X,Y):- nextto(X,Z),sameline(Z,Y).

I convert "left/right" into "nextto" relationship between people. And the code works fine when two peoples are actually in same lines. But if I try:

?- sameline(a,c)

Where "a" and "c" are not in same line. The program goes into infinite loop until runs out of local stack. I assume it keeps trying to find variable "Z" between "X" and "Y" and if not found, the program will just create another "Z" to keep searching. I've seen the typical ancestor example using recursive call:

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).

which makes sense. But how is my code different from the ancestor example? Apparently nextto(a,j) will return false, but why the loop won't stop?

It's my second day of learning Prolog, so advanced use of Prolog might not help :(.

Thanks.

What do you expect for: sameline(c,X) , e.g what values of X makes it succeed?? — coder
From my code, sameline(c,i) sameline(c,j) sameline(c,k) will all return true since they are in same line. — Monkey
Would the answer be the same if was right(k,j) ?? Then we would have c ->i -> j and k->j would these be two lines or k is considered in the line c,i,j?? — coder
I suppose you mean right(j,k)? This will cause error to the program. But the question here I don't need to consider this situation. Assume all the conditions are well ordered. — Monkey
Yes I meant right(j,k), Assume all the conditions are well ordered you mean that the lines will be clear (e.g we will not have examples like c ->i -> j and k->j) ?? — coder

coder coder · Accepted Answer · 2017-10-23T19:29:46

If you trace:

?- sameline(a,c).

you will see that it falls into cycle a <-> b due to:

nextto(X,Y):- left(X,Y);left(Y,X);right(X,Y);right(Y,X).

In the rule above you let next(a,b) and next(b,a) to succeed but you need only one to succeed in order not to fall into cycle:

In trace you can see:

Redo: (8) sameline(a, c) ? creep    %OK trying to succeed sameline(a,c)
   Call: (9) nextto(a, _884) ? creep

The above continues with:

Call: (10) left(a, _884) ? creep
   Exit: (10) left(a, b) ? creep     %Only b succeeds left(a,_)
   Exit: (9) nextto(a, b) ? creep
   Call: (9) sameline(b, c) ? creep  %OK trying to succeed recursively

sameline(b,c).

But this ends up calling:

Redo: (9) sameline(b, c) ? creep
   Call: (10) nextto(b, _884) ? creep
   Call: (11) left(b, _884) ? creep
   Fail: (11) left(b, _884) ? creep
   Redo: (10) nextto(b, _884) ? creep
   Call: (11) left(_882, b) ? creep
   Exit: (11) left(a, b) ? creep
   Exit: (10) nextto(b, a) ? creep
   Call: (10) sameline(a, c) ? creep   % Same thing we began due to cycle

In order to solve this issue if I understand right what you're trying to do, you should define:

nextto(X,Y):- left(X,Y);right(Y,X).
sameline(X,Y):- nextto(X,Y).
sameline(X,Y):- nextto(X,Z),sameline(Z,Y).

This definition of nextto/2 forces to follow one path-line and not fall into cycle.

Examples:

?- sameline(c,X).
X = i ;
X = j ;
X = k ;
false.

?- sameline(c,i).
true ;
false.

?- sameline(a,c).
false.

EDIT

If you want nextto/2 to handle cycles, one way solving it is keeping a list of what you've visited:

sameline(X,Y):- sameline(X,Y,[X]).

nextto(X,Y):- left(X,Y);left(Y,X);right(X,Y);right(Y,X).
sameline(X,Y,_):- nextto(X,Y).
sameline(X,Y,L):- nextto(X,Z),\+member(Z,L),sameline(Z,Y,[Z|L]).

Prolog indirect relationship

1 Answers

EDIT