How to check if any statisfying clause exists in Prolog without backtracking through all different paths?
prolog, prolog-cut, prolog-setof
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.
Problem
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`?