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?

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.

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

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.

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 ?-