避免谓词中的递归

Question

我对以下谓词有以下问题，如何从两个谓词中删除递归调用 f(T,S1)。

流量模型： (i,o)

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

这是一个技巧问题，我的序言不太好。第二个谓词总是失败。=> 可以删除，但是第二个呢？如我所见，此方法是一个列表元素计数器。谢谢

这可能吗？

Answer 1

下面的怎么样？效率很高！-)

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

Answer 2

好的，这是一个复杂的问题。你认为这是一个技巧问题，但它真的是一个吗？我们如何确定？我会让 library(clpfd) 替我思考。首先我会重写你的程序：

:- use_module(library(clpfd)).

fx([],0).
fx([H|T],S):-
    fx(T,S1),
    S1 #> 2,
    S #= S1 + H.
fx([_|T],S):-
    fx(T,S1),
    S1 #=< 2,
    S #= S1 + 1.

（还有一点：将这些测试放在递归之后两次将使该程序需要成倍增加的推理，但让我们坚持下去...）

所以我想以最一般的方式对该程序进行推理。因此，我不会采取具体的价值观，然后试图找出一个理论。相反，我会问非常笼统的问题（使用 SICStus）：

| ?- assert(clpfd:full_answer).
yes
| ?- length(L,N), fx(L,S).
   L = [],
   N = 0,
   S = 0 ?
;
   L = [_A],
   N = 1,
   S = 1 ?
;
   L = [_A,_B],
   N = 2,
   S = 2 ?
;
   L = [_A,_B,_C],
   N = 3,
   S = 3 ?
;
   L = [_A,_B,_C,_D],
   N = 4,
   _A+3#=S,
   _A in inf..sup,
   S in inf..sup ?
;
   L = [_A,_B,_C,_D,_E],
   N = 5, ...

所以请查看 N = 0 到 N = 3 的答案：不涉及任何约束，有效地忽略列表 [_A,_B,...] 的所有元素。但是，从 N = 4 开始，第一个元素 _A 现在会影响 "sum" S，因为等式 S #= _A+3 成立！值越大，事情变得越来越复杂。

无论如何，我不明白这怎么会是一个骗人的问题。最后三个元素被忽略。好吧，这是一种把戏。但其他因素（或至少其中一些）会影响结果！

避免谓词中的递归

Avoid recursion in predicate

prolog