CODEWITHSUNDEEP
prologtrace
Måns Nilsson
Måns Nilsson

Reputation: 451

Prolog predicate only returns one result

I have a predicate called spider with the following code:

person(ada).
person(beda).
person(calle).
knows(ada,beda).
knows(ada,calle).
knows(beda,calle).

% Returns true for arguments X and Y if either knows(X,Y) or knows(Y,X) is true.
xknowsy(X,Y) :- knows(X,Y).
xknowsy(X,Y) :- knows(Y,X).

subsetsof([],[]).
subsetsof([A|B],[A|D]) :- subsetsof(B,D).
subsetsof([A|B],D) :- subsetsof(B,D).

dontknowlist([]).
dontknowlist([A]).
dontknowlist([A,B|C]) :- not(xknowsy(A,B)), dontknowlist([A|C]), dontknowlist([B|C]).

listknowsconspirator([],C).
listknowsconspirator([A|B],C) :- knowssomeone(A,C), listknowsconspirator(B,C).

knowssomeone(A,[]).
knowssomeone(A,[B|C]) :- xknowsy(A,B).
knowssomeone(A,[B,C|D]) :- knowssomeone(A,[C|D]).

spider(X) :- person(X), findall(A,xknowsy(X,A),B), subsetsof(B,C), dontknowlist(C),!,
findall(E,person(E),F), removespider(F,X,G), removeconspirators(G,C,L),!,
listknowsconspirator(L,C),!.

removespider([],X,L) :- L = [].
removespider([A|B],X,L) :- A = X, L = B.
removespider([A|B],X,L) :- not(A = X), removespider(B,X,M), L = [A|M].

removeconspirators([],D,L) :- L = [].
removeconspirators(E,[],L) :- L = E.
removeconspirators([A],[B],L) :- A = B, L = [].
removeconspirators([A],[B],L) :- not(A = B), L = [A].
removeconspirators([A,B|C],[D],L) :- A = D, L = [B|C].
removeconspirators([A,B|C],[D],L) :- not(A = D), removeconspirators([B|C],[D],M), L = [A|M].
removeconspirators([A|B],[S,T|U],L) :- removeconspirators([A|B],[S],M),
removeconspirators(M,[T|U],N), L = N.

Calls to spider(ada), spider(beda) and spider(calle) all separately return true. But when I call spider(X), I don't get all three solutions for X. I just get the first solution, i.e. X = ada. I don't understand why because person(X) makes sure that I get all three possible X values to run the rest of the predicate through. Calling spider(X) in trace mode does not appear to reveal any obvious explanations, but my compiler SWI-Prolog just seems to be ignoring the other cases. Why aren't all three solutions printed out when calling spider(X)?

Upvotes: 2

Views: 894

Answers (1)

coder
coder

Reputation: 12972

The reason of the above behavior is the cuts that you use in spider/1 predicate. If you remove them and write:

spider(X) :- person(X), findall(A,xknowsy(X,A),B), subsetsof(B,C),dontknowlist(C),
findall(E,person(E),F), removespider(F,X,G), removeconspirators(G,C,L),
listknowsconspirator(L,C).

then if you query:

?- final_spider(X).
X = ada ;
X = ada ;
X = ada ;
X = beda ;
X = beda ;
X = beda ;
X = calle ;
X = calle ;
X = calle.

This gives all the solutions via backtracking, but it gives the right solutions more than one times. This is not easy to avoid by using ! because it will cut some right answers too. To keep right solutions only once you could write one more predicate:

final_spider(X):-findall(Y,spider(Y),L),sort(L,L1),member(X,L1).

Now if you query:

?- final_spider(X).
X = ada ;
X = beda ;
X = calle.

It gives the right solutions only once.

Upvotes: 0

Related Questions