4

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

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，但这将是非常程序化的，不幸的是我不太适合在 prolog 中完成这项工作。有什么想法或建议吗？

4

3 回答 3

4

你的第一个子句应该是

sum([], 0).

随着这种变化，空虚的true回报消失了，你留下了一个问题：第三个子句颠倒了求和的逻辑。它应该是

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

因为s/1左参数中的项数sum/2应该等于右参数中的项数。

于 2012-03-14T18:54:34.307 回答
3

The best way to localize the problem is to first simplify your query:

?- sum([0],S).

true
?- sum([],S).

true

Even for those, you get as an answer that any S will do. Like

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

Since [] can only be handled by your fact, an error must lie in that very fact. You stated:

sum([], Sum).

Which means that the sum of [] is just anything. You probably meant 0.

Another error hides in the last rule... After fixing the first error, we get

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

Here, the last clause is responsible. It reads:

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

Recursive rules are relatively tricky to read in Prolog. The simplest way to understand them is to look at the :- and realize that this should be an arrow ← (thus a right-to-left arrow) meaning:

provided, that the goals on the right-hand side are true
we conclude what is found on the left-hand side

So, compared to informal writing, the arrows points into the opposite direction!

For our query, we can consider the following instantiation substituting Xs with [] and X with 0.

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

So this rule now reads right-to-left: Provided, sum([0],s(Sum)) is true, ... However, we do know that only sum([0],0) holds, but not that goal. Therefore, this rule never applies! What you intended was rather the opposite:

sum([s(X)|Xs], s(Sum)):-sum([X|Xs],Sum).
于 2012-03-14T18:56:16.570 回答
0

我并没有真正遵循您的逻辑，所有看似无关的s(X)结构都在浮动。

做这样的事情不是更容易更简单吗？

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

  • 空列表的和为 0。
  • 非空列表的总和是通过将列表的头部与列表尾部的总和相加得到的。

根据该定义，序言直接如下：

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!
于 2012-03-15T22:46:31.943 回答