CODEWITHSUNDEEP
listprologinfinite-loop
gnat
gnat

Reputation: 1

Stopping infinite loop in Prolog

I'm trying to return distinct items in a list. I've come up with the following code. I seem to run into a problem when checking the members of the list using member(X,Y), and it runs into an infinite loop. 

get_unique(Y, [H|T]) :-
   memberchk(H, Y)->  get_unique(Y, T) ; get_unique([H|T], T).
get_unique(_, []) :- true.

final_list(X, L) :-
   get_unique(Y, L), member(X,Y).

There are two input cases: 

?- final_list(dog,[dog,cat,bat,dog]). 

true;
true;
true;
true;
(infinitely)

In this case I would expect just 

true;
false.

The other input case:

?- final_list(X,[dog,cat,bat,dog]).

X = dog;
X = cat;
X = bat;
true ;
true ;
true ;
true ;
true ;
true ;
(infinitely)

In this case I would expect just 

X = dog;
X = cat;
X = bat;
false.

I tried to do some debugging and I think I can see that member(X,Y) is generating the infinite loop -- tracing steps seen below. I don't know how to stop this, such that member stops checking once it returns bat. 

X = bat ;
   Redo: (9) lists:member(_6632, [dog, cat, bat|_6882]) ? creep
   Exit: (9) lists:member(_6632, [dog, cat, bat, _6632|_6888]) ? creep
   Exit: (8) final_list(_6632, [dog, cat, bat, dog]) ? creep
true ;
   Redo: (9) lists:member(_6632, [dog, cat, bat, _6886|_6888]) ? creep
   Exit: (9) lists:member(_6632, [dog, cat, bat, _6886, _6632|_6894]) ? creep
   Exit: (8) final_list(_6632, [dog, cat, bat, dog]) ? creep
true ;
   Redo: (9) lists:member(_6632, [dog, cat, bat, _6886, _6892|_6894]) ? creep
   Exit: (9) lists:member(_6632, [dog, cat, bat, _6886, _6892, _6632|_6900]) ? creep
   Exit: (8) final_list(_6632, [dog, cat, bat, dog]) ? creep
true ;
   Redo: (9) lists:member(_6632, [dog, cat, bat, _6886, _6892, _6898|_6900]) ? creep
   Exit: (9) lists:member(_6632, [dog, cat, bat, _6886, _6892, _6898, _6632|...]) ? creep
   Exit: (8) final_list(_6632, [dog, cat, bat, dog]) ? creep
true ;

Thank you!

Upvotes: 0

Views: 103

Answers (1)

false
false

Reputation: 10102

Try get_unique/2 alone:

?- get_unique(Y,[dog,cat,bat,dog]).
   Y = [dog,cat,bat|_A].
%                   ^^^

Thus, Y is only a partial list, but not a (real) list. It comprises all lists with three or more elements.

The second clause should read get_unique([], []). to avoid this problem. And also the first needs some rearrangement:

get_unique(Y, [H|T]) :-
   ( memberchk(H, T) ->  get_unique(Y, T) ; Y = [H|Y1], get_unique(Y1, T) ).
%                 ^^                        ^^^^^^^^^^             ^^
get_unique([], []).

But still, your definition makes some odd assumptions:

?- final_list(X,[dog,Cat]).
   X = dog, Cat = dog.

So it forces variables to become one specific value.

There is no clean way out of this, except by reconsidering member/2. See this answer for a clean solution. Here is the answer memberd/2 produces:

?- memberd(X,[dog,Cat]).
   X = dog
;  X = Cat, dif(Cat,dog)
;  false.

So the answer says: X = dog as before and additionally, X = Cat but only if Cat is different to dog.

Upvotes: 2

Related Questions