这个 Prolog 代码是如何工作的——随机播放两个列表

Question

我有以下代码，有效，可以随机播放两个列表：

shuffle([], [], []).
shuffle([X|Xs], Ys, [X|Zs]):-
          shuffle(Xs, Ys, Zs).
shuffle(Xs, [Y|Ys], [Y|Zs]):-
          shuffle(Xs, Ys, Zs).

我分别理解了每个部分。第一个子句接收两个列表，一个带有 X 的是 head，Xs 是 tail。在结果中我们 "take" 只有第一个列表的 head。与第二个子句相同——我们不将 Xs 作为结果，只取 Y.

的 head

Prolog 递归地分离列表，然后统一它们。

这里我不明白的是它是如何工作的？它结束"taking out"所有的Xs之后，就"moves"到第二个子句，取Ys？是什么触发 Prolog 这样做？

谢谢。

Answer 1

例如，当您尝试在 Prolog 中证明一个目标时：shuffle([a],[c],L).Prolog 所做的是在数据库中搜索以查找与谓词洗牌相关的规则。

在这种情况下，第二条和第三条规则都出现了，所以你有两个选项 - 在 Prolog 中调用的选择点：

第一选择点：我们检查第二条规则：shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).并将其应用到我们的目标中，我们得到[X|Xs] = [a]（所以X = a, Xs = []），Ys = [c]，L的形式是[a|Zs]，最后递归调用shuffle([],[c],Zs)。这个目标现在只匹配第三条规则，我们得到 Zs = [c|Zs'] 并再次递归地调用 shuffle([],[],Zs')，现在只有第一条规则匹配，我们得到 Zs' = []。因此，从检查的第一个案例中，我们得到 Zs = [a,c]。现在我们还剩下一个案例：

第二个选择点：我们检查第三条规则：shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs).并将其应用到我们的目标中，我们得到Xs = [a], [Y|Ys] = [c]（所以Y = c, Ys = []），而L的形式是[c|Zs]，最后递归调用shuffle([a],[],Zs)。这个目标现在只匹配第二条规则，我们得到 Zs = [a|Zs'] 并再次递归地调用 shuffle([],[],Zs')，现在只有第一条规则匹配，我们得到 Zs' = []。所以从第二个案例中我们得到 Zs = [c,a].

所以最后我们得到了两个解决方案。如您所见，Prolog 对选择点进行深度优先分析，因为它找到第一个选择点并对其进行检查，然后继续进行第三个选择点，依此类推。这里明显的问题是你能想象双元素列表的选择点数量，例如 shuffle([a,b],[c,d],L) ??这将是四个选择点，对于 Xs,Ys 的一般情况，选择点太多了。

Answer 2

避免所有 X、Y 和 Z 部分，关于工作代码我们能说些什么：

您从 shuffle([1,2],[a,b],L). 这样的查询开始，Prolog 尝试通过解决三个 shuffle 规则来解决它。
一个洗牌规则可以自己解决，但只针对空列表，其他两个依赖于解决shuffle规则的另一种情况。
无论找到什么解决方案必须去shuffle -> shuffle -> [shuffle....] -> empty lists。它必须。如果它根本无法匹配任何随机播放，它将回答 "false" 并且您的代码将无法运行。如果它永远在洗牌之间反弹，它将无限循环并且不给出任何答案并且您的代码将无法运行。它确实有效，所以它必须从头开始链接，通过随机组合，直到空列表。

Prolog 将尝试从规则的顶部开始求解：

From the top:

A) shuffle([1,2],[a,b],L).  -no->  shuffle([],[],[]).
B) shuffle([1,2],[a,b],L).  -??->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
B) shuffle([1,2],[a,b],L).  -??->  shuffle([X=1|Xs=[2]],Ys=[a,b],[X=1|Zs=??]) :- shuffle(Xs=[2],Ys=[a,b],Zs).

% A) fails as [1,2] does not match with []
% B) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle(Xs=[2],Ys=[a,b],Zs).



From the top:

A) shuffle([2],[a,b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([2],[a,b],Zs).  -??->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
B) shuffle([2],[a,b],Zs).  -??->  shuffle([X=2|Xs=[]],Ys=[a,b],[X=2|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [2] does not match with []
% B) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle(Xs=[],Ys=[a,b],Zs).



From the top:

A) shuffle([],[a,b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([],[a,b],Zs).  -no->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[a,b],Zs).  -??->  shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[a,b],Zs).  -??->  shuffle(Xs=[],[Y=a|Ys=[b]],[Y=a|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [a,b] does not match with the second []
% B) fails as [] does not match with [X|Xs]
% C) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle([],[b],Zs).



From the top:

A) shuffle([],[b],Zs).  -no->  shuffle([],[],[]).
B) shuffle([],[b],Zs).  -no->  shuffle([X|Xs],Ys,[X|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[b],Zs).  -??->  shuffle(Xs,[Y|Ys],[Y|Zs]):- shuffle(Xs,Ys,Zs).
C) shuffle([],[b],Zs).  -??->  shuffle(Xs=[],[Y=b|Ys=[]],[Y=b|Zs=??]):- shuffle(Xs,Ys,Zs).

% A) fails as [b] does not match with the second []
% B) fails as [] does not match with [X|Xs]
% C) partially binds but is missing Zs. Solving to try and find the Zs is now:

shuffle([],[],Zs).



From the top:

A) shuffle([],[],Zs).  -no->  shuffle([],[],[]).

% A) succeeds. Zs can be []

这是一个完整的链条，从原点，经过四次洗牌，到空列表。在这条链中，Zs 被构造为 [1|?] 然后 [1|[2|?]] 然后 [1|[2|[a|?]]] 然后 [1|[2|[a|[b|?]]]] 然后 [1|[2|[a|[b|[]]]]] 这是完整的，没有遗漏任何东西。绑定到第一个结果的 L 输入。

经过洗牌B B C C。

但是搜索space还没有穷尽，可能会有更多的答案。如果你要求它们，它会沿着链条展开，回到它本可以采取不同路径的地方。它可以跳过 shuffle([X|Xs].. 而不是解决 shuffle([X|Xs].. 并向下钻进 shuffle(Xs。

具有大量值的两个 shuffle 谓词共同构成了一个反弹模式，该模式以三个空列表案例结束：

[1,2],[a,b],Unknown
        \
         \
          \ ? shuffle shuffle shuffle
          /
         /
         \
      [],[],[]

一条逻辑连接链是B B C C A。另一个链是 B C B C A 导致下一个答案 L=[1,a,2,b].

[1,2],[a,b],Unknown
       /   \       
      /     \
      \      \ B C B A
B B C C\     /
       |    /
       |    \
      [],[],[]

一旦它一路回溯，在每个选择中将洗牌换成另一个，然后沿着链向下到空列表，它将找到 6 条路径，6 种方式来反弹洗牌。

随着列表变长，链也会变长。当它开始回溯链条并撤消其步骤以寻找其他方法时，就会有更多的方法。更多的选择点，所以它会找到更多的解决方案 - 与输入的长度成正比。

这个 Prolog 代码是如何工作的——随机播放两个列表

How does this Prolog code really work - Shuffle two Lists

recursion

shuffle

list

prolog

non-deterministic