Don't repeat solutions in Prolog

Question

Suppose you have a database with the following content:

son(a, d).
son(b, d).
son(a, c).
son(b, c).

So a and b are sons of d and c. Now you want to know, given a bigger database, who is brother to who. A solution would be:

brother(X, Y) :-
    son(X, P),
    son(Y, P),
    X \= Y.

The problem with this is that if you ask "brother(X, Y)." and start pressing ";" you'll get redundant results like:

X = a, Y = b;
X = b, Y = a;
X = a, Y = b;
X = b, Y = a;

I can understand why I get these results but I am looking for a way to fix this. What can I do?

Adding a link to why results are repeated would be helpful to readers. — GiriB, Jan 31 '17 at 15:35

score 6 · Answer 1 · answered Feb 23 '13 at 15:59

Prolog will always try to find every possible solution available for your statements considering your set of truths. The expansion works as depth-first search:

son(a, d).
son(b, d).
son(a, c).
son(b, c).

brother(X, Y) :-
    son(X, P),
    son(Y, P),
    X \= Y.

                         brother(X, Y)
       _______________________|____________________________        [son(X, P)]
      |               |                  |                 |
X = a, P = d     X = b, P = d       X = a, P = c      X = a, P = b
      |               |                  |                 |  
      |              ...                ...               ...
      |
      | (X and P are already defined for this branch;
      |  the algorithm now looks for Y's)
      |__________________________________________                  [son(Y, d)]
                |                                |
      son(a, d) -> Y = a               son(b, d) -> Y = b
                |                                |
                |                                |                 [X \= Y]
      X = a, Y = a -> false            X = a, Y = b -> true
                                                 |
                                                 |
                                  solution(X = a, Y = b, P = d)

But, as you can see, the expansion will be performed in all the branches, so you'll end up with more of the same solution as the final answer. As pointed by @Daniel Lyons, you may use the setof built-in.

You may also use the ! -- cut operator -- that stops the "horizontal" expansion, once a branch has been found to be valid, or add some statement that avoids the multiple solutions.

For further information, take a look at the Unification algorithm.

I actually understood this. I was trying to find a way to fix the problem and I did. Thanks for the very elaborate answer. — petermlm, Feb 25 '13 at 00:36

score 5 · Answer 2 · edited Apr 29 '15 at 18:11

5

First, I would advise against updating the Prolog database dynamically. For some reasons, consider the article "How to deal with the Prolog dynamic database?".

You could use a combination of the builtin setof/3 and member/2, as @DanielLyons has suggested in his answer.

As yet another alternative, consider the following query which uses setof/3 in a rather unusual way, like this:

?- setof(t,brother(X,Y),_).
X = a, Y = b ;
X = b, Y = a.

edited Apr 29 '15 at 18:11

false

10,264
13
101
209

answered Apr 29 '15 at 14:39

repeat

18,496
4
54
166

1

I liked this solution. I think this case can be solved using `bagof` instead of setof too. Am I wrong? – eightShirt Nov 20 '20 at 22:44

score 4 · Answer 3 · answered Feb 23 '13 at 15:55

You can eliminate one set with a comparison:

brother(X, Y) :-
   son(X, P),
   son(Y, P),
   X \= Y, X @< Y.

?- brother(X, Y).
X = a,
Y = b ;
X = a,
Y = b ;
false.

Since X and Y will be instantiated both ways, requiring X be less than Y is a good way to cut the solutions in half.

Your second problem is that X and Y are brothers by more than one parent. The easiest solution here would be to make your rules more explicit:

mother(a, d).
mother(b, d).
father(a, c).
father(b, c).

brother(X, Y) :-
  mother(X, M), mother(Y, M),
  father(X, F), father(Y, F),
  X \= Y, X @< Y.

?- brother(X, Y).
X = a,
Y = b ;
false.

This method is very specific to this particular problem, but the underlying reasoning is not: you had two copies because a and b are "brothers" by c and also by d—Prolog was right to produce that solution twice because there was a hidden variable being instantiated to two different values.

A more elegant solution would probably be to use setof/3 to get the solutions. This can work even with your original code:

?- setof(X-Y, (brother(X, Y), X @< Y), Brothers).
Brothers = [a-b].

The downside to this approach is that you wind up with a list rather than Prolog generating different solutions, though you can recover that behavior with member/2.

This can solve the problem of repeating solutions but raises another. Asking ":- brother('a', 'b')." returns true, but asking "brother('b', 'a')." returns false. But thanks for the answer. It's a nice and simple trick that does solve part of what I wanted. — petermlm, Feb 25 '13 at 00:39
That's true, but it would be very bad Prolog style to want `brother(b, a)` to be true but not generated by `brother(X, Y)`. In general you don't want to fail to generate acceptable solutions. — Daniel Lyons, Feb 25 '13 at 05:05

score 0 · Answer 4 · answered Feb 23 '13 at 17:50

0

This should work. But I think it can be improved (I am not a Prolog specialist):

brother(X, Y) :-
    son(X, P1),
    son(Y, P1),
    X @< Y,
    (son(X, P2), son(Y, P2), P1 @< P2 -> false; true).

answered Feb 23 '13 at 17:50

Benoît Guédas

801
7
25

Like I said to @Daniel Lyons. This is also a nice solution for the problem but it raises another. Asking ":- brother('a', 'b')." returns true, but asking "brother('b', 'a')." returns false. Thanks for the answer, I didn't know the notation of your last line. – petermlm Feb 25 '13 at 00:44

score 0 · Answer 5 · edited Feb 24 '13 at 17:37

0

If you're using Strawberry Prolog compiler,you won't get all the answers by typing this:

?- brother(X, Y),
   write(X), nl,
   write(Y), nl.

In order to get all the answers write this:

?- brother(X, Y),
   write(X), nl,
   write(Y), nl,
   fail.

I hope it helps you.:)

edited Feb 24 '13 at 17:37

Rubens

14,478
11
63
92

answered Feb 23 '13 at 20:18

Faeze

118
1
7

Actually I am using swipl and can't test your solution. But it's always nice to have the answer for the many available platforms! – petermlm Feb 25 '13 at 00:45

score -2 · Accepted Answer · answered Feb 23 '13 at 23:28

I got to an answer.

% Include the dictionary
:- [p1]. % The dictionary with sons

:- dynamic(found/2).

brother(X, Y) :-
    % Get two persons from the database to test
    son(X, P),
    son(Y, P),

    % Test if the two persons are different and were not already used
    testBrother(X, Y).

% If it got here it's because there is no one else to test above, so just fail and retract all
brother(_, _) :-
    retract(found(_, _)),
    fail.

testBrother(X, Y) :-
    X \= Y,
    \+found(X, Y),
    \+found(Y, X),

    % If they were not used succed and assert what was found
    assert(found(X, Y)).

It always returns fails in the end but it succeeds with the following.

brother(X, Y). % Every brother without repetition
brother('Urraca', X). % Every brother of Urraca without repetition
brother('Urraca', 'Sancho I'). % True, because Urraca and Sancho I have the same father and mother. In fact, even if they only had the same mother or the same father it would return true. A little off context but still valid, if they have three or more common parents it would still work

It fails with the following:

brother(X, X). % False because it's the same person
brother('Nope', X). % False because not is not even in the database
brother('Nope', 'Sancho I'). % False, same reason

So like this I can, for example, ask: brother(X, Y), and start pressing ";" to see every brother and sister without any repetition.

I can also do brother(a, b) and brother(b, a), assuming a and b are persons in the database. This is important because some solutions would use @< to test things and like so brother(b, a) would fail.

So there it is.

It works, but it's not something I would want to do in my own code. I consider the dynamic store to be kind of a last resort, a way to hack around the usual try/bind/fail/unbind unification Prolog wants to do. Having dynamic state that magically appears and disappears during what appear to be purely-logical predicates is a lot of machinery and a lot of places to hide bugs. If I saw this in a codebase, I'd worry that things like this might be happening all over, making the software hard to isolate and debug. — Daniel Lyons, Feb 25 '13 at 05:10
I see. Thanks for you feedback (In here and the other comment) I do agree with what you said, but I really needed this like I showed. — petermlm, Feb 25 '13 at 14:37

Don't repeat solutions in Prolog

6 Answers6

Linked