Search code examples
recursionprologprogram-transformation

Avoid double recursive call in Prolog

I have this Prolog code:

f([ ],-1).

f([H|T],S):- f(T,S1), S1>0, !, S is S1+H.

f([_|T],S):- f(T,S1), S is S1.

How can I avoid the second (redundant) recursive call f(T,S1), in the third clause, the overall effect of predicate remaining the same?

I know that this could be done by defining an additional predicate.

How can such predicate be defined?

Solution

  • First we re-write it a little bit to see the similarities better,

    f([ ],-1).
f([H|T],S) :- f(T,S1), S1>0, !, S is S1+H.
f([H|T],S) :- f(T,S1),          S is S1.

    Next we factor out the equal part, and replace its continuation with the new predicate that will do the same thing as was done before, with the same logical variables as were involved there before:

    f([ ],-1).
f([H|T],S) :- f(T,S1), additional_predicate(S1,S,H).

    Now all that's left to do is to write the same goals under the new name:

    additional_predicate(S1,S,H):- S1>0, !, S is S1+H.
additional_predicate(S1,S,H):- S is S1.

    And that's that.

    Put simply, after the call to f(T,S1) is done, S1 is already calculated, so there's no need to recalculate it anew.