recursion - 避免 Prolog 中的双重递归调用

Question

我有这个 Prolog 代码：

f([ ],-1).

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

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

如何避免第二个（冗余）递归调用 f(T,S1)，在第三个子句中，谓词的整体效果保持不变？

我知道这可以通过定义一个额外的谓词来完成。

如何定义这样的谓词？

Answer 1

| ?- 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 ...

这会敲响警钟吗？

好吧，这就是我要回应的内容：

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

虽然这现在终止并失败，f(L, 0)而原始定义循环。如果您也坚持这种等效性：

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

Answer 2

首先我们稍微重写一下以更好地查看相似之处，

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.

接下来我们分解出相等的部分，并用新的谓词替换它的延续，该谓词将执行与之前相同的操作，并使用与之前涉及的相同逻辑变量：

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

现在剩下要做的就是以新名称编写相同的目标：

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

就是这样。

简而言之，在调用f(T,S1)完成后，S1已经计算好了，所以不需要重新计算。