避免 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已经计算好了，不需要重新计算。

避免 Prolog 中的双重递归调用

Avoid double recursive call in Prolog

recursion

prolog

program-transformation