Prolog中列表中的元素总和几乎无需解释

Question

我是prolog编程的初学者,我希望你谦虚并帮助我解决这个困惑

我正面临一个问题来计算prolog的总和,我有答案,但对我来说并不是那么清楚.答案是:

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

我不明白的是Sum1程序将如何以及如何按步骤工作

它会首先检查第一个条件,list_sum([], 0).而条件不满足它会将列表分成两部分Head,Tail然后呢？

我希望你接受一个小小的初学者并给他一些时间来纠正他的困惑.
谢谢你们

Answer 1

这是经典的递归方法 - 您需要熟悉它才能理解 Prolog。

您的规则有两个子句 - 一个用于空列表，另一个用于非空列表。空列表子句表示空列表的元素总和为零（这是完全合理的）。这被称为“递归的基本情况”。每个终止递归规则都必须有一个基本情况。

第二个条款稍微复杂一些。它大致是这样说的：“要计算非空列表中元素的总和，首先切掉初始元素，然后计算得到的较短列表中元素的总和。调用 sum Sum1。现在Total通过添加值来计算的初始元素的值Sum1。

第二个子句递归地将列表分解为一系列较短的列表，直到它们成为空列表。此时第一个子句介入，提供空列表的总和。

考虑这个例子：

list_sum([12, 34, 56], X)
    list_sum([34, 56], <unknown-1>)
        list_sum([56], <unknown-2>)
            list_sum([], 0)         ---> succeeds with Total bound to 0
        <unknown-2> becomes 0 + 56  ---> succeeds with Total bound to 56
    <unknown-1> becomes 0 + 56 + 34 ---> succeeds with Total bound to 90
X becomes 0 + 56 + 34 + 12          ---> succeeds with X bound to 102

这是有效的，因为递归链中的每个调用级别都有自己的变量 for Sum1。这些值开始时没有限制，但是一旦递归调用链“触底反弹”，Sum1s 就会开始获取每个先前级别计算的值。最终，调用链到达顶层，将最终结果绑定到调用者传递的变量上。

Answer 2

程序中有一个很小的错误 - 该行Total = Head + Sum意味着这Total是一个+带有两个参数的结构.你可能意味着is取代=意义算术评估.但最好的是#=改用.

在你的问题中,你问的是该程序将做什么.这在面向命令("命令式")语言中是一个非常合理的问题,因为你可以从程序中获得的唯一含义是它的逐步操作.但在Prolog中,事情有点不同.您仍然可以尝试逐步思考,但迟早您会意识到事情会变得非常复杂,仅仅因为Prolog没有一个控制流,而是两个同时被调用(AND-和OR-控制).甚至"数据结构"也不同......

但是有一种方法可以阅读Prolog程序,它在命令式语言中没有对应程序:您可以将程序理解为参数之间的关系.通过这种方式,您可以专注于关系的样子而不是程序方面.毕竟,如果描述的关系是错误的,那么询问程序如何执行此操作毫无意义.

那么让我来重温你的程序:

:- use_module(library(clpfd)).
list_sum([], 0).
list_sum([E|Es], S) :-
   S #= E+T,
   list_sum(Es, T).

它首先检查第一个条件list_sum([],0).如果条件不满足,它会将列表分为H和T两部分吗？

你的问题意味着有一个单一的控制流程("虽然这是一个典型的构造,暗示它").但它也可能有所不同.考虑查询:

?- list_sum(Xs,0).
Xs = [] ;
Xs = [0] ;
Xs = [_G1710, _G1713],
_G1710+_G1713#=0 ...

在这里,我们询问存在哪些列表,其总和为0.现在,你的"同时"不再有意义.

我们得到的答案是:空列表; 列表0; 一个两元素列表,其中元素之和为0; 等等...

理解这些程序的最好方法是将它们理解为如下关系:

list_sum([], 0:空列表的总和为0.

现在,规则在:-从右到左的箭头方向上读得最好:

• list_sum(Es, T).:*提供的Es是一个总和T和... 的列表

• S #= E+T:... S是E加T...

• :- ......然后我们可以得出结论......

• list_sum([E|Es], S):S是列表的总和[E|Es].

通过这种方式,可以理解这些事情,而无需过多地参考程序细节.还有更多的东西,比如理解终止,看看故障切片.