我有以下代码，可以打乱两个列表：
shuffle([], [], []).
shuffle([X|Xs], Ys, [X|Zs]):-
shuffle(Xs, Ys, Zs).
shuffle(Xs, [Y|Ys], [Y|Zs]):-
shuffle(Xs, Ys, Zs).
我分别理解每个部分。第一个子句接收两个列表，一个列表的X是头部，Xs是尾部。在结果中，我们只"取"第一个列表的头部。与第二条相同——我们不以Xs为结果，只接受Y的负责人。
Prolog递归地分隔列表，然后统一它们。
我不明白的是它是如何工作的？在它结束了"取出"所有Xs之后，它只是"移动"到第二句，拿Ys？是什么促使Prolog这样做？
谢谢。
例如，当你试图在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的一般情况，选择点太多了。
避开所有 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.
但搜索空间并没有用尽，可能会有更多的答案。如果你要求它们，它会沿着链条回到一个可以走不同路径的地方。与其解决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 种方式在洗牌中反弹。
当您使列表变长时，链也会变长。当它开始回溯链条以寻找其他方式时，就会有更多的步骤。更多的选择点，所以它会找到更多的解决方案 - 与输入的长度成正比。