Prolog loop control not working as expected

Question

I have the following prolog code. The link predicate refers to another file containing various links such as:

link(b,brown,j)

I am using the member predicate to attempt to control the looping in this route program. The idea is if I have been to a certain position before, the program will not try to go down that route.

However, when I try to trace the program to see where it is going wrong, when it checks to see if the position is a member in the positions list, the first position is already in the list so the program always tries another route after that point when it shouldn't. Anyone know how to fix this?

member(X,[X|_]).
member(X,[_|Xs]):- member(X,Xs).

route(X,X,[X],_).
route(X,Z,[X|Path],Positions):- 
    link(X,Colour,Y),
    \+member([Y,Colour],Positions),             
    route(Y,Z,Path,[[Y,Colour]|Positions]),
    !.

Please, do not vandalize your question. If there is an issue with this post, you can alert a moderator by raising custom-flag. — Tunaki, Apr 22 '16 at 11:19
You do not have the right to delete your own content once posted. Please refrain from further attempts to self-vandalize. — Magisch, Apr 22 '16 at 11:20

false · Answer 1 · 2022-08-19T12:01:32.213

Some minor comments first: You do not need that cut at all. If you really want to restrict the predicate to exactly one answer, do it at the top using once/1. That is not only conceptually cleaner, it is even more efficient.

The other problem you had is related to Prolog's unsafe negation. If you, accidentally as you did, hand over a goal that is too general, the negation will always fail. In other words: negation is next-to-broken in Prolog. There are two ways out: Either produce an error for such cases or simply use a better definition like non_member/2.

Let's see what would have happened with non_member/2 in place:

link(b,brown,j).

route(X,X,[X],_).
route(X,Z,[X|Path],Positions):-
    link(X,Colour,Y),
    % \+member([Y,Colour],Positions),
    non_member([Y,Colour],Positions),
    route(Y,Z,Path,[[Y,Colour]|Positions]).

non_member(E, Es) :-
   maplist(dif(E), Es).

?- route(X,Y,Path,Rs).
   Y = X, Path = [X]
;  X = b, Y = j, Path = "bj", Rs = []
;  X = b, Y = j, Path = "bj", Rs = [_A],
   dif([j,brown],_A)
;  X = b, Y = j, Path = "bj", Rs = [_A,_B],
   dif([j,brown],_A), dif([j,brown],_B)
;  X = b, Y = j, Path = "bj", Rs = [_A,_B,_C],
   dif([j,brown],_A), dif([j,brown],_B), dif([j,brown],_C)
;  X = b, Y = j, Path = "bj", Rs = [_A,_B,_C,_D],
   dif([j,brown],_A), dif([j,brown],_B), dif([j,brown],_C),
   dif([j,brown],_D)
;  X = b, Y = j, Path = "bj", Rs = [_A,_B,_C,_D,_E],
   dif([j,brown],_A),  dif([j,brown],_B), dif([j,brown],_C),
   dif([j,brown],_D), dif([j,brown],_E)
; ... .

So all answers describe the same Path = "bj" (short form for [b,j]). But the last argument now is a list of elements that all must be different to [j,brown]. So the best would have been:

route(X, Y, Path) :-
   route(X, Y, Path, []).

And here is an alternate definition reusing path/4. I am not really sure what you mean by these colors. Nevertheless:

clink(X-_, Y-Color) :-
   link(X, Color, Y).

route(X, Y, Path) :-
   path(clink, Path, X-none, Y-_).

or even shorter using library(lambda):

route(X, Y, Path) :-
   path(\ (Xl,_)^(Yl^C)^clink(Xl,C,Yl), Path, X-none, Y-_).

Prolog loop control not working as expected

1 Answers1