Prolog蓄电池换向

Question

我遇到了一个问题，对于我提出的每一个Prolog问题，我的答案都会被反转。这是因为我学到了如何使用累加器来逆转列表，而现在我似乎能够解决问题的唯一方法是使用类似的程序，它给出了答案，但也逆转了列表。

例如，当被要求编写一个程序，用第三个参数替换第一个参数中第二个参数的所有实例，并将结果列表作为第四个参数时，我编写了以下代码：

replace(L, A, B, X):-  
    accrep(L, [], A, B, X).   

accrep([H | T], Y, A, B, X):-
    H = A,  
    accrep(T, [B | Y], A, B, X). 

accrep([H | T], Y, A, B, X):-  
    H \= A,  
    accrep(T, [H | Y], A, B, X). 

accrep([], X, _, _, X).

这确实在技术上解决了问题，但也颠倒了清单，这是不被要求的，当我把正确的答案倒过来时，我怀疑任何人都会对此印象深刻。但是我想不出一种避免这种情况的方法，添加取消列表的代码似乎很荒谬，而我一开始就不应该逆转它。

有人能告诉我如何在不遇到这个问题的情况下使用累加器吗？我也有过同样的问题多个其他简单的程序。

谢谢，亚历克斯。

Answer 1

我认为你使用累加器是因为你在考虑一个程序性的解决方案。只要避开它，您的代码就会简单得多，并将解决问题。这是一个开始，请完成它。

replace(L, A, B, X):-
    accrep(L, A, B, X).

accrep([], _, _, []).
accrep([A|R], A, B, [B|S]) :- accrep(R, A, B, S).
....

Answer 2

下面是一种看待它的方法:当您使用累加器进行递归(通常作为参数对实现)时，它通常如下所示：

generic(..., Final, Final, ...).
generic(..., Previous, Final, ...) :-
    ...
    generic(..., Next, Final, ...).

递归子句

• 接收累加器的Previous值。
• 计算Next累加器值。
• 并从对调用方的递归调用中返回Final累加器值。

这在实现计数器时最为明显，其中所有累加器参数都是整数。Previous是旧的计数器值，Next是多一个，Total是最终结果：

counter(..., Total, Total, ...).
counter(..., Previous, Total, ...) :-
    ...
    Next is Previous+1,
    counter(..., Next, Total, ...).

您所做的非常类似:每个累加器参数都是一个专用列表：Previous是到目前为止构建的列表，Next是带有前面附加元素的Previous，Final是最终列表。

revlist(..., Final, Final, ...).
revlist(..., Previous, Final, ...) :-
    ...
    Next = [New|Previous],
    revlist(..., Next, Final, ...).

到现在为止还好。现在，请记住，Prolog对于数据结构的构造非常放松。您可以在它们中留下漏洞(以空闲变量的形式)，并在以后(通过实例化这些变量)填充它们。对于列表，这意味着您可以有一个带有未实例化尾的列表，然后再提供其余的。把它和累加器的想法放在一起，并让所有累加器参数都是list，：Previous是列表的末尾，通过实例化Previous扩展列表到另一个list元素。这为您提供了一个新的尾，Next，您将其传递到递归中。您可以看到，与前一个模式的唯一区别是list元素的构造方式：

fwdlist(..., Final, Final, ...).
fwdlist(..., Previous, Final, ...) :-
    ...
    Previous = [New|Next],
    fwdlist(..., Next, Final, ...).

成功后，该谓词的调用方将在第一个累加器参数中找到列表的开头，在第二个参数中找到尾。列表与创建元素的顺序相同，可以通过将Final设置为[]来终止该列表。

注：(1)在最后一种情况下，Final参数是可以消除的--我只是把它放在那里来显示对称性。(2)整个解释是程序性的，就输入/输出参数而言-在现实中，列表示例将在多种模式下工作。