prolog - Prolog 中设置并集运算 : explanation

Question

union([H|T],[],[H|T]).     
union([],[H|T],[H|T]).    
union([H|T], SET2, RESULT) :- member(H,SET2), union(T,SET2,RESULT).    
union([H|T], SET2, [H|RESULT]) :- not(member(H,SET2)), union(T,SET2,RESULT).

<小时/>

我能够理解它正在遍历第一个列表并根据元素是否是第二个列表的成员进行添加。我明白了逻辑。然而，工作流程对我来说很神秘，一旦第一个列表耗尽，它就会将“第二个列表”的元素添加到结果中。

请有人举一个简单的例子，比如union([1,2], [2,3], Result)，并解释一下工作流程。

Answer 1

我假设您正在调用 union/3 并实例化第一个和第二个参数。第三个参数可以在调用时未实例化，并在返回时与两个列表的并集统一，或者如果它已经实例化，则可以用于检查它是否与前两个列表的(有序)并集匹配。

第一个子句指出，如果第二个参数是空列表并且第一个列表至少有一个元素，那么并集就是第一个列表。同样，第二个子句指出，如果第一个参数是空列表并且第二个列表至少有一个元素，那么并集就是第二个列表。

第三个子句在第一个列表上递归并检查第二个列表以查看该项目是否已存在。在这种情况下，它只是用第一个列表的尾部调用自己。

第四个子句测试第一个列表的头部，以检查它是否不包含在第二个列表中，并与尾部递归调用(就像第三个子句一样)。然而，在递归返回时，它将该项目添加到第三个列表的头部，从而将该项目添加到联合中。

请注意，在您的实现中，两个空集的并集总是会失败。您可以通过修改第一个或第二个子句以允许空列表来解决此问题，或者针对这种情况添加另一个子句。例如

union([],[],[]).

现在让我们看看当我们调用 union([1,2],[2,3], Result) 时会发生什么:

前两个子句将无法匹配，因为它们都不是空列表。

我们输入第三个子句并检查元素 1 不是第二个列表的成员，因此失败。

我们现在尝试第四个子句并测试元素 1 不在第二个列表中，因此我们调用 union([2], [2,3], Result) ，我们标记这个执行点(*1)。

前两个子句再次无法匹配，因此我们输入第三个子句。这里我们测试元素 2 确实包含在第二个列表中，所以我们调用 union([], [2,3], Result) ，我们标记这个执行点(*2)

现在第一个子句失败，因为第一个参数是空列表。我们现在输入第二个子句，将第三个参数与第二个列表 ([2,3]) 统一起来。

此时我们返回到 (*2)，此时 Result 被实例化为 [2,3]。该子句到此结束，因此我们将第三个参数与 [1,2,3] 绑定(bind)，然后返回到 (*1)。

我们现在位于 (*1)，其中 Result 以及第三个参数被实例化为 [1,2,3]。

这给了我们第一个结果[1,2,3]。

然而，当我们成功进入(*2)时，留下了一个选择点，所以如果我们要求Prolog搜索另一个答案，它仍然必须尝试union([2], [2,3]，结果)。

所以我们输入第四个子句来测试 2 是否不是 [2,3] 的成员，这失败了，所以 Prolog 会告诉我们没有其他答案。