list Prolog中列表中元素的总和

Sum of elements in list in Prolog

提问by Rok Kralj

list_sum([], 0).
list_sum([Head | Tail], TotalSum) :-
    list_sum(Tail, Sum1),
    Total = Head + Sum1.

This code returns true. If I replace Total = Head + Sum1with Total is Head + Sum1, then it will return the value. But what I should replace it with to get the result like this:

此代码返回true. 如果我替换Total = Head + Sum1为Total is Head + Sum1，那么它将返回该值。但是我应该用它替换它以获得这样的结果：

?- list_sum([1,2,0,3], Sum).
Sum = 1+2+0+3 ; % not to return value 6!!!

采纳答案by gusbro

Note that in the second clause of your procedure TotalSum is never instantiated. You should have received a warning by the interpreter when consulting your code.

请注意，在过程 TotalSum 的第二个子句中，从未实例化。在查阅您的代码时，您应该已经收到解释器的警告。

Here's my suggestion:

这是我的建议：

list_sum([Item], Item).
list_sum([Item1,Item2 | Tail], Total) :-
    list_sum([Item1+Item2|Tail], Total).

The first clause deals with the base case, when there is only one element left in the list, that is your result.

第一个子句处理基本情况，当列表中只剩下一个元素时，这就是您的结果。

The second clause deals with the recursion step. It grabs the first two items of the list and performs a recursive call replacing those two items with a new term Item1+Item2.

第二个子句处理递归步骤。它获取列表的前两项并执行递归调用，用新项 Item1+Item2 替换这两项。

回答by Rok Kralj

The answer is simple:

答案很简单：

sum_list([], 0).
sum_list([H|T], Sum) :-
   sum_list(T, Rest),
   Sum is H + Rest.

This code works in only one direction - this means - it does not allow you to generate lists with that specific sum. But since the set of such lists is infinite, that would not be practical anyways.

此代码仅在一个方向上起作用 - 这意味着 - 它不允许您生成具有该特定总和的列表。但是由于此类列表的集合是无限的，因此无论如何这都不实用。

回答by Rohan

The program is

该程序是

list_sum([],0).

list_sum([Head|Tail], TotalSum):-
list_sum(Tail, Sum1),
TotalSum is Head+Sum1.

now if the query is

现在如果查询是

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

answer is

答案是

Sum = 10

回答by repeat

In Prolog (+)/2is a binary infixoperator. This allows us to write A+Binstead of +(A,B).

在 Prolog 中(+)/2是一个二元中缀运算符。这允许我们编写A+B而不是+(A,B).

?- current_op(_,yfx,+).   % left-associative binary infix operator
true.

(+)/2associates to the left, so 1+2+3is a short for (1+2)+3.

(+)/2左侧的关联，因此1+2+3是 的缩写(1+2)+3。

(.)/2associates to the right, so [1,2,3]is short for .(1,.(2,.(3,[]))).

(.)/2联想到右边，所以[1,2,3]是.(1,.(2,.(3,[]))).

To get parenthesization right, we use an auxiliary predicate with an extra "accumulator" argument:

为了获得正确的括号，我们使用一个带有额外“累加器”参数的辅助谓词：

list_sum([X|Xs],S) :-
   list_sum0_sum(Xs,X,S).

list_sum0_sum([],    S ,S).
list_sum0_sum([X|Xs],S0,S) :-
   list_sum0_sum(Xs,S0+X,S).

Sample query:

示例查询：

?- list_sum([1,2,0,3],S).
S = 1+2+0+3.

回答by Nicholas Carey

If you want to transform a list of numbers into an additive expression, from

如果要将数字列表转换为加法表达式，请从

[1,2,3]

to

到

1 + 2 + 3

1 + 2 + 3

you could do something like this, using something like a difference list:

你可以做这样的事情，使用类似差异列表的东西：

list_to_additive_expr( [] , 0 ).
list_to_additive_expr( [X|Xs] , X + RHS ) :-
  sum_of( Xs , RHS ).

Alternatively, you could use an accumulator:

或者，您可以使用累加器：

list_to_additive_expr( Xs , Expr ) :-
  list_to_additive_expr( Xs , 0 , Expr )
  .

list_to_additive_expr( []     , Expr , Expr ) .
list_to_additive_expr( [X|Xs] , RHS , Expr ) :-
  sum_of( Xs , X + RHS , Expr )
  .

I believe you'll find the first style is not properly tail recursiveand so won't get optimized into a loop via tail recursion optimization(TRO) — and so, if the list is sufficiently long, will get a stack overflow. The second approach should have TRO applied and should work for lists of any length.

我相信您会发现第一种样式不是正确的尾递归，因此不会通过尾递归优化(TRO)优化为循环——因此，如果列表足够长，则会导致堆栈溢出。第二种方法应该应用 TRO，并且应该适用于任何长度的列表。

What is TRO, you might ask? Here's Wikipedia with an answer for you:

你可能会问什么是 TRO？这是维基百科给你的答案：

In computer science, a tail call is a subroutine call that happens inside another procedure and that produces a return value, which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If a subroutine performs a tail call to itself, it is called tail-recursive. This is a special case of recursion.

Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination, or tail call optimization.

在计算机科学中，尾调用是在另一个过程中发生的子程序调用，它产生一个返回值，然后由调用过程立即返回。然后称调用站点处于尾部位置，即在调用过程的末尾。如果子程序对自身执行尾调用，则称为尾递归。这是递归的一种特殊情况。

尾调用很重要，因为它们可以在不向调用堆栈中添加新堆栈帧的情况下实现。当前过程的大部分帧不再需要，可以用尾调用的帧代替，适当修改（类似于进程的覆盖，但用于函数调用）。然后程序可以跳转到被调用的子程序。生成此类代码而不是标准调用序列称为尾调用消除或尾调用优化。