prolog 中列表的总和

Question

我正在阅读《序言的艺术》一书，我发现一个练习，内容是“定义关系 sum(ListOfIntegers,Sum)，如果 Sum 是 ListOfIntegers 的总和，则该关系成立，而不使用任何辅助谓词”。我想出了这个解决方案：

sum([],Sum).
sum([0|Xs], Sum):-sum(Xs, Sum).
sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).

这并不完全按照我想要的方式工作。

?- sum([s(s(0)),s(0),s(s(s(0)))],X).
true ;
false.

我原以为 X 会是

s(s(s(s(s(s(0))))))

我认为问题是我必须在第一次“迭代”中将 Sum '初始化' 为 0，但这将是非常程序性的，不幸的是我不太容易在序言中实现这一点。有什么想法或建议吗？

Answer 1

定位问题的最佳方法是首先简化查询：

?- sum([0],S).

true
?- sum([],S).

true

即使对于那些，你也会得到这样的答案 任何 S 会做。喜欢

?- sum([],s(s(0))).
yes

自从 [] 只能根据你的事实来处理，错误一定就在于这个事实。你说：

sum([], Sum).

这意味着总和 [] 就是任何东西。你的意思可能是0。

另一个错误隐藏在最后一条规则中......修复第一个错误后，我们得到

?- sum([0],Sum).
Sum = 0
?- sum([s(0)],Sum).
no

在这里，最后一个子句负责。上面写着：

sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).

在 Prolog 中，递归规则相对难以阅读。了解它们的最简单方法是查看 :- 并意识到这应该是一个箭头 ← （因此是一个从右到左的箭头），意思是：

前提是右侧的目标是真实的

---

我们得出左侧的结论

因此，与非正式写作相比，箭头指向相反的方向！

对于我们的查询，我们可以考虑以下实例化替换 Xs 和 [] 和 X 与 0。

sum([s(0)| [] ], Sum) :- sum([0| []],s(Sum)).

所以这条规则现在从右到左读：假如， sum([0],s(Sum)) 是真的， ...然而，我们确实知道，只有 sum([0],0) 成立，但不是那个目标。因此，这条规则永远不适用！你的意图恰恰相反：

sum([s(X)|Xs], s(Sum)):-sum([X|Xs],Sum).

Answer 2

您的第一个子句应该读取

sum([], 0).

. 与此更改有变化，空泡生成的acticetagcode返回消失，您留下了一个问题：第三个子句逆转求和的逻辑。它应该是

sum([s(X)|Xs], s(Sum)) :- sum([X|Xs], Sum).

.

因为左参数中的生成族常规术语的数量应该等于右参数中的它们的数量。

Answer 3

我真的不是追随你的逻辑，与所有看似的外来生古代古代码结构漂浮在一起。

做这样的事情不会更容易，更简单？

首先，以简单的英语定义您的解决方案，因此：

• 空列表的总和为0.
• 通过将列表的头部添加到列表尾部的总和来获得非空列表的总和。

从该定义中，Prolog直接遵循：

sum( []     , 0 ) .  % the sum of an empty list is 0.
sum( [X|Xs] , T ) :- % the sum of an non-empty list is obtained by:
  sum( Xs , T1 ) ,   % - first computing the sum of the tail
  T is X + T1        % - and then, adding that the to head of the list
  .                  % Easy!

.