prolog - 这个置换算法是如何工作的

Question

ar([],[]).
ar([p(_,_)|L],L1):-ar(L,L2),L1=L2.
ar([p(X,Y)|L],L1):-ar(L,L2),L1=[p(X,Y)|L2].

（p 代表点，坐标为 X 和 Y）

请帮助我了解结果是如何构造的，尤其是 L1 获得新值的部分，谢谢！

Answer 1

谓词的定义ar/2类似于powerset函数，是以下的语法变体（X仅限于 的术语p/2）：

% clause 1: base case
ps([], []).

% clause 2: omit the element X
ps([_X|Y], Z) :-
    ps(Y, Z). 

% clause 3: keep the element X
ps([X|Y], [X|Z]) :-
    ps(Y, Z).

谓词ps/2（和你的ar/2）基本上回溯以将第一个参数中列表的所有子列表绑定到第二个参数的子列表。它通过第二个和第三个子句表示的选择来实现这一点：在构造新列表时省略或保留一个列表元素。

考虑一下 Prolog 在执行目标时做了什么ps([a,b],L)：

• ps([_|[b]], Z) :- ps([b], Z).（通过第 2 条， drop a）。
  • ps([b|[]], Z) :- ps([], Z).（通过第 2 条，drop b；注意[b]= [b|[]]）。
    • ps([], Z)绑定Z = []（通过第 1 条，给出解决方案 1）。
  • ps([b|[]], [b|Z]) :- ps([], Z).（通过第 3 条，保留b）。
    • ps([], Z)绑定Z = []（通过第 1 条，给出解决方案 2）。
• ps([_|[b]], [a|Z]) :- ps([b], Z).（通过第 3 条，保留a）。
  • ps([b|[]], Z) :- ps([], Z).（通过第 2 条， drop b）。
    • ps([], Z)绑定Z = []（通过第 1 条，给出解决方案 3）。
  • ps([b|[]], [b|Z]) :- ps([], Z).（通过第 3 条，保留b）。
    • ps([], Z)绑定Z = []（通过第 1 条，给出解决方案 4）。

达到第 1 条“基本情况”的每个最深层次都返回调用堆栈。每种情况都会导致以下结果：

1. 删除a和b：[]
2. 放下a，保持b：[b]
3. 保持a，放下b：[a]
4. 保留a和b：[a,b]

因此，我们可以回溯生成[]、和[b]，即 的四个子列表。[a][a,b][a,b]

Answer 2

首先，请注意，此过程不计算置换，而是计算一种子列表：删除了“一些”点的列表，其中“一些”以一般形式表示（其中一个解决方案是空列表，也是其他解决方案是原始列表），假设输入列表格式正确。

如果输入列表格式不正确（它有一项不是“点”），则该过程将失败。

现在我们来解释一下 的三个子句ar/2，这是一个递归过程：

第一条，

ar([], []).

声明如果第一个参数是空列表，那么第二个参数也是输入列表；即对于一个空列表，唯一符合程序规则的“子列表”也是一个空列表。这也是递归过程的基本情况。

第二条，

ar([p(_,_)|L], L1):-ar(L, L2), L1=L2.

可以在不使用L2变量的情况下重写，因为它最终会统一为L1：

ar([p(_,_)|L], L1):-ar(L, L1).

该子句跳过输入列表的头部并继续递归。在递归返回时，它会将结果列表（ar/2调用的第二个参数）与子句头部的第二个参数统一起来。

第三条，

ar([p(X,Y)|L], L1):-ar(L, L2), L1=[p(X,Y)|L2].

L2通过在子句头部构建结果列表，可以再次在不使用变量的情况下重写：

ar([p(X,Y)|L], [p(X,Y)|L1]):-ar(L,L1).

该子句将获取输入列表的头部，继续使用尾部递归，然后将子句头部的第二个参数与所取的项目和递归的结果列表统一起来。也就是说，它将保留输入列表的项（头）以及递归的结果。

还要注意，这个过程是不可逆的，如果调用第一个参数未实例化而第二个参数实例化，它将永远循环。