list - 这个 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。在结果中，我们仅“获取”第一个列表的头部。与第二个子句相同 - 我们不采用 Xs 作为结果，仅采用 Y 的 head。

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

我不明白的是它是如何工作的？当它“取出”所有X结束后，它只是“移动”到第二个子句，取出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 = [] code>), 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 的一般情况来说，选择点太多了。