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?

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`. — lurker, Nov 23 '13 at 20:26

false · Accepted Answer · 2021-08-13T17:00:13.967

5

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.

edited Aug 13 '21 at 17:00

answered Nov 23 '13 at 20:18

false

10,264
13
101
209

1

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. – SQB Nov 23 '13 at 20:57
4

@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. – false Nov 23 '13 at 21:02
1

Define `mysibling(X,Y) :- setof(t,sibling(X,Y),_).` There is not much more to it than that. What else were you thinking of? – false Nov 27 '13 at 10:16
2

Or: `exists(XGoal) :- setof(t,XGoal,_)` Now you can even use quantifiers. – false Nov 27 '13 at 10:18
2

Yes, that works! I could've sworn that didn't unify, but it does. I must've messed up somewhere. Anyway, bounty earned :) – SQB Nov 27 '13 at 11:14
I have provided a solution using a cut [here](https://stackoverflow.com/a/68753360/2326961) giving multiple answers. – Géry Ogam Aug 12 '21 at 07:41

score 2 · Answer 2 · answered Aug 12 '21 at 07:35

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

answered Aug 12 '21 at 07:35

Géry Ogam

6,336
4
38
67

2

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. – Will Ness Aug 13 '21 at 12:31
2

`sameparent(charlie, P), P = diane.` fails, yet `P = diane, sameparent(charlie, P).` succeeds. Now have these two persons the same parent or not? – false Aug 13 '21 at 18:45
@WillNess Yes I have cheated a bit. Do you know how to define `person/1` in terms of `parent/2`? – Géry Ogam Aug 15 '21 at 11:24
@false You are right, so there does not seem to be a correct program using only cuts. – Géry Ogam Aug 15 '21 at 11:25
@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. – Will Ness Aug 15 '21 at 12:57

SQB · Answer 3 · 2021-08-20T10:29:10.780

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.

Will Ness · Answer 4 · 2021-08-20T17:43:05.960

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

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

4 Answers4

Linked