Don't repeat solutions in Prolog
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
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.