How to check if any statisfying clause exists in Prolog without backtracking through all different paths?

Question

Let's say I have the following:

parent(alice, charlie).
parent(bob, charlie).
parent(bob, diane).
parent(alice, diane).
parent(bob, eve).
parent(alice, eve).    

% people are siblings of each other if they share a parent 
% and aren't the same person.
sibling(A, B) :-
  parent(X, A),
  parent(X, B),
  B \= A.

Now if I ask for the siblings of Diane, I get Charlie and Eve — twice, once through Bob and once through Alice. I only want each once.
I don't think I can use a cut here, as that would prevent backtracking altogether. What I would like, is a way to check if any exists.

Paraphrasing

sibling(A, B) :-
  ∃(parent(X, A), parent(X, B)),
  B \= A.

---

I tried several cuts, but none worked.
I tried findall/3 on (parent(X, A), parent(X, B)) and checking if the resulting list is non-empty, but that doesn't unify A or B.

---

Using setof/3 as suggested below works, but I really want to find a way to incorporate it in the definition of sibling/2, instead of having to use it in the question. I'd really like to be able to do the following:

?- sibling(diane, X).
X = charlie ;
X = eve ;
false.

or this

?sibling(X, Y).
X = charlie,
Y = diane ;
X = charlie,
Y = eve ;
X = diane,
Y = charlie ;
X = diane,
Y = eve ;
X = eve,
Y = charlie ;
X = eve,
Y = diane ;
false.

---

Like I said below, I have a solution for this specific case. What I would like, and what I'm setting a bounty for, is a general solution.

Instead of

sibling(A, B) :-
  setof(D, X^(parent(X, A), parent(X, D)), Ds),
  member(B, Ds),
  B \= A.

I'd like to do

sibling(A, B) :-
  exists(X^(parent(X, A), parent(X, B))),
  B \= A.

which unifies A and B.

How do I define exists/1?

Radiotelephone

I had a very similar case and ended up doing what @false suggested with setof. I also did play with a few techniques to avoid putting redundant answers in the results, but they often were more complex than just using setof. – Unloose

Answer 1

Using cut in Prolog is very delicate. Most cuts are essentially incorrect, but work still in certain situations. You could use a cut here, provided you want exactly one answer. But since you want the entire set, you are out of luck: You need to explore all answers to determine that set.

Fortunately, there is an elegant shortcut (pun intended) for that: setof/3. So ask

?- setof(t, sibling(diane, S), _).

For this usage of setof/3, the last argument is of no interest. It is actually [t].

For a general purpose exists/1, define

exists(XGoal) :- setof(t, XGoal, _).

This allows the use of existential quantifiers.

Eliason

Yeah, that works. And the first argument is of no interest either. setof(_, sibling(diane, S), _). does the trick. I'm still trying to find a way to incorporate it in the definition of sibling, though. – Radiotelephone

@SQB: _s in setof are often a bug (in the 2nd argument). Yes, it works also with a first argument _ but here you are exploring some pretty scary limits of setof/3. Better keep it some atom. t is pretty idiomatic. – Eliason

Define mysibling(X,Y) :- setof(t,sibling(X,Y),_). There is not much more to it than that. What else were you thinking of? – Eliason

Or: exists(XGoal) :- setof(t,XGoal,_) Now you can even use quantifiers. – Eliason

Yes, that works! I could've sworn that didn't unify, but it does. I must've messed up somewhere. Anyway, bounty earned :) – Radiotelephone

I have provided a solution using a cut here giving multiple answers. – Abigael

Answer 2

Here is a version using only the cut predicate !/0:

person(alice).
person(bob).
person(charlie).
person(diane).
person(eve).
parent(alice, charlie).
parent(bob, charlie).
parent(bob, diane).
parent(alice, diane).
parent(bob, eve).
parent(alice, eve).

sibling(X, Y) :-
  person(X),
  person(Y),
  X \= Y,
  sameparent(X, Y).

sameparent(X, Y) :-
  parent(P, X),
  parent(P, Y),
  !.

We do not put the predicate !/0 in the predicate sibling/2 to allow backtracking to the goal sibling(X, Y) after the first common parent has been found. Instead we put the predicate !/0 in a new predicate sameparent/2. We also add a person predicate because the goal X \= Y requires its X and Y to be instantiated. See this document for more information.

A query:

?- sibling(diane, Y).
Y = charlie
Y = eve

Another query:

?- sibling(X, Y).
X = charlie,
Y = diane
X = charlie,
Y = eve
X = diane,
Y = charlie
X = diane,
Y = eve
X = eve,
Y = charlie
X = eve,
Y = diane

Sanson

I uv'd but actually you've cheated a little bit here by adding the person/1 predicate that wasn't there. :) the original Q asks for a solution using only parent/2 as the fact base. to be compliant, you'd have to define person in terms of parent too. – Hussite

sameparent(charlie, P), P = diane. fails, yet P = diane, sameparent(charlie, P). succeeds. Now have these two persons the same parent or not? – Eliason

@WillNess Yes I have cheated a bit. Do you know how to define person/1 in terms of parent/2? – Abigael

@Eliason You are right, so there does not seem to be a correct program using only cuts. – Abigael

@Maggyero I suspect this is equivalent, in essence, to what the question is asking. :) usually using dif helps in such cases, to turn operational definitions into the proper declarative ones. – Hussite

Answer 3

parent(alice, charlie).
parent(bob, charlie).
parent(bob, diane).
parent(alice, diane).
parent(bob, eve).
parent(alice, eve).
    
% people are siblings of each other if they share a parent 
% and aren't the same person.
sibling(A, B) :-
  setof(D, X^(parent(X, A), parent(X, D)), Ds),
  member(B, Ds),
  B \= A.
    
?- sibling(X, Y).
X = charlie,
Y = diane ;
X = charlie,
Y = eve ;
X = diane,
Y = charlie ;
X = diane,
Y = eve ;
X = eve,
Y = charlie ;
X = eve,
Y = diane ;
false.

---

Now I'm wondering how to extract this to a method exists/1, for general use.

Radiotelephone

Answer 4

So, as seen in the accepted answer, we can run

?- setof(P, (parent(P,diane), parent(P,X), X\=diane), _).

or

?- setof(P, (parent(P,diane), parent(P,X)), _), X\=diane.

to get what you want.

Hence we can define a binary predicate "exists A such that B holds":

exists(A, B):- setof( A, B, _).

and use it as

sibling_v1(A, B):- exists( P, (parent(P,A), parent(P,B)) ), B \= A.

or as

sibling_v2(A, B):- exists( P, (parent(P,A), parent(P,B), B \= A) ).

to define the desired predicates.

But it'll still run through all the possible paths to find out all the possible solutions (just reporting each once). For how could it be certain to have not missed some, otherwise?

57 ?- exists( P, (parent(P,diane), parent(P,X), X\=diane)).
X = charlie ;
X = eve.

58 ?- exists( P, (parent(P,diane), parent(P,X), writeln([P,X]), X\=diane)).
[bob,charlie]
[bob,diane]
[bob,eve]
[alice,charlie]
[alice,diane]
[alice,eve]
X = charlie ;
X = eve.

59 ?- 

Hussite