I have the following Prolog Rule:
p(X,Y):- q(Y,X), r(Y), s(Y), t(X).
It is known that r(Y) and s(Y) have only one solution, while q(X,Y) and p(X,Y) have several solutions.
The task is to optimise the Rule with an auxillary predicate.
My guess is to put a Cut between s(Y) and t(X) to prevent useless backtracking.
What kind of auxillary predicate could one write to optimise this rule?
Be cautious with cuts. For example if - on your first try - you have choosen the right Y but the wrong X (for t(X)) using a cut in the predicates body will provide a wrong answer.
Example:
r(1).
s(1).
t(X):- member(X,[7,8,9,6]).
q(Y,X):- member(X,[1,2,3,6]), member(Y,[3,4,5,6,1]).
p(X,Y):- q(Y,X), r(Y), s(Y), t(X).
?- p(X,Y).
X = 6,
Y = 1.
But with
p(X,Y):- q(Y,X), r(Y), s(Y), !, t(X).
?- p(X,Y).
false.
If you are using the cut within the aux predicate the cut does not discard 'right' answers because the backtracking is still allowed in the predictae p/2 even if aux/2 was passed once:
aux(Y) :- r(Y), s(Y), !.
p(X,Y):- q(Y,X), aux(Y), t(X).
?- p(X,Y).
X = 6,
Y = 1.
I just saw that there is no improvement by using the aux predicate. However using
aux(Y) :- r(Y), !, s(Y).
or
aux(Y) :- !, r(Y), s(Y).
might improve the speed if s/1 is computative expensive. The second solution should only be used if Y was instantiated before. Also reordering the predicates could result in a speed up.
