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?

Answer 1

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.

Answer 2

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.