CODEWITHSUNDEEP
recursionprologprogram-transformation
Dasher
Dasher

Reputation: 49

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?

Upvotes: 0

Views: 280

Answers (2)

false
false

Reputation: 10102

?- length(L,_), f(L,R).
   L = [], R = -1
;  L = [_A], R = -1
;  L = [_A,_B], R = -1
;  L = [_A,_B,_C], R = -1
;  L = [_A,_B,_C,_D], R = -1
;  L = [_A,_B,_C,_D,_E], R = -1
;  L = [_A,_B,_C,_D,_E,_F], R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G], R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G,_H], R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G,_H,_I], R = -1
;  L = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J], R = -1
;  ... .

Does this ring a bell?

Well, here is what I would respond:

f(L, -1) :-
   length(L, _).

Although this now terminates and fails for f(L, 0) whereas the original definition looped. In case you insist on this equivalence as well:

f(L, MinusOne) :-
   length(L, _),
   MinusOne = -1.

Upvotes: 1

Will Ness
Will Ness

Reputation: 71075

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.

Upvotes: 0

Related Questions