prologprolog-cutprolog-setof

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


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?


Solution

  • 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.