如何使用prolog在带有交替符号的列表中获得结果？

Question

该程序将生成列表的交替结果。例如，{5,6,1}将是5-6+1.

alternate(L,X) :-
   alternate(L,0,K,_).

alternate([],X,_,_).

alternate([H|T],A,p,S) :- !,
    AA is A + H,
    alternate(T,AA,m,S).

alternate([H|T],A,m,S) :- !,
    AA is A - H,
        alternate(T,AA,p,S).

以下是跟踪结果：

alternate([5,6,1],S).
   Call: (10) alternate([5, 6, 1], _11626) ? creep
   Call: (11) alternate([5, 6, 1], 0, p, _12084) ? creep
   Call: (12) _12128 is 0+5 ? creep
   Exit: (12) 5 is 0+5 ? creep
   Call: (12) alternate([6, 1], 5, m, _12222) ? creep
   Call: (13) _12266 is 5-6 ? creep
   Exit: (13) -1 is 5-6 ? creep
   Call: (13) alternate([1], -1, p, _12360) ? creep
   Call: (14) _12404 is -1+1 ? creep
   Exit: (14) 0 is -1+1 ? creep
   Call: (14) alternate([], 0, m, _12498) ? creep//I expect it to return the X = 0 here.
   Exit: (14) alternate([], 0, m, _12542) ? creep
   Exit: (13) alternate([1], -1, p, _12586) ? creep
   Exit: (12) alternate([6, 1], 5, m, _12630) ? creep
   Exit: (11) alternate([5, 6, 1], 0, p, _12674) ? creep
   Exit: (10) alternate([5, 6, 1], _11626) ? creep
true.

当没有更多的元素时，我使用备用([]，X，，)来返回X，但是我不明白为什么它不能工作。

Answer 1

如果到达列表的末尾，则需要将累加器中迄今计算的值(第二个参数)短路为“最终结果”：

而不是：

alternate([],X,_,_).

alternate([],X,_,X).

启动时，从p开始，累加器设置为0。关于成功，论点4将包含最终结果：

alternate(L,X) :-
   alternate(L,0,p,X).

因此：

alternate(L,X) :-
   alternate(L,0,p,X).

alternate([],X,_,X).

alternate([H|T],A,p,S) :- !,
    AA is A + H,
    alternate(T,AA,m,S).

alternate([H|T],A,m,S) :- !,
    AA is A - H,
        alternate(T,AA,p,S).

?- alternate([1,2,3,4],X).
X = -2.

奖金:作为DCG

这一项是用非尾递归方式编写的，因此只需要对每个调用进行“最后和”，然后根据谓词成功计算一个新的“最后和”：

alternate(List,Sum) :- phrase(alternate_p(Sum),List).

alternate_p(0)   --> [].
alternate_p(Sum) --> [X], alternate_n(TailSum), { Sum is TailSum+X }.

alternate_n(0)   --> [].
alternate_n(Sum) --> [X], alternate_p(TailSum), { Sum is TailSum-X }.

?- alternate([1,2,3,4],Sum).
Sum = -2 ;  % any additional solutions?
false.      % nope

奖金:使用折叠/4

这一切都是以尾递归的方式在列表上积累一个值，我们可以避免自己编写递归，切换到“函数编码”并使用foldl/4。我们只需要编写一个谓词，这里的alternator/3为每个列表元素调用，从“左侧”获取“内容”，并构建“新内容”并将其移到“右边”。在我们的例子中，“[Sum,Multiplier]”是一对

% alternator(Element,FromLeft,ToRight)

alternator(Element,[Sum,Multiplier],[NewSum,NewMultiplier]) :-
   NewSum is Sum + Multiplier*Element,
   NewMultiplier is Multiplier*(-1).
   
% alternate(List,Sum) is an application of foldl/4:

alternate(List,Sum) :-
   foldl(alternator,List,[0,1],FoldlResult),
   FoldlResult = [Sum,_FinalMultiplier].

再一次：

?-  alternate([1,2,3,4],Sum).
Sum = -2.