为什么这个 Prolog 谓词不统一？

Question

我正在编写一个谓词来查找 A* 迭代的所有可能的后继状态，并将它们放入类似 [(cost, state), ...] 的列表中，目前处于此状态：

addSuccessors(L, [], _).
addSuccessors(L, [X|T], OrigList) :- memb(OrigList, Index, X),
                                     add((X, Index), L, List2),
                                     addSuccessors(List2, T, OrigList).
addSuccessors(L, [X|[]], OrigList) :- memb(OrigList, Index, X),
                                     add((X, Index), L, L2),
                                     addSuccessors(L2, [], OrigList).

Add 添加一些内容到在列表末尾， memb 获取列表的第（索引）个元素。我知道它们有效，当我查看底部谓词中的 L2 时，我得到类似这样的结果，

?- addSuccessors(X, [1500, 3670], [0, 0, 0, 1500, 3670]).
X = [] ;
[ (1500, 3), (3670, 4)]
X = [] ;
X = [_G1175] ;
[_G1175, (1500, 3), (3670, 4)]
X = [_G1175] ;
X = [_G1175, _G1181] ;
[_G1175, _G1181, (1500, 3), (3670, 4)]
X = [_G1175, _G1181] ;
...

这非常令人沮丧，因为 [(1500, 3), (3670, 4)] 列表是我调用后希望 X 成为的列表所以它看起来像是在做我想做的事，只是不是……在我想做的地方。

请问我该如何解决这个问题？

Answer 1

自从我在 Prolog 中编程以来已经有一段时间了，但我认为您需要将正在构建的列表与返回的列表分开（即添加另一个参数）。您的 [X|[]] 规则应该绑定输出变量而不是递归。

Answer 2

想想 L 实际上是如何获得它的初始值的。事实是事实并非如此。您想要做的是从头开始构建一个列表，因此您需要从一个空列表开始，而不是一个未绑定的变量。解决此问题的一种方法是编写一个包装谓词，它允许当前谓词充当累加器谓词。

这可能看起来像这样，其中 addSuccessors_acc 将包含您已经定义的子句。

addSuccessors(L, X, Y) :-
    addSuccessors_acc(L,[],X,Y).

这个想法是，addSuccessors_acc 谓词的第二个参数充当累加器，它是通过每次递归调用构建的列表。然后，在累加器谓词的基本情况下，您只需将累加器变量与第一个参数统一，即可传递最终列表。例如：

 addSuccessors_acc(L,L,_,_).

另外，正如 ergosys 指出的那样，你的第三个子句实际上可以是基本情况。由于您正在处理列表中的最后一个元素，因此无需递归 - 所做的只是将基本情况延迟一次额外的调用。