Prolog 如何将 2 个列表打印为一个列表，而不需要任何附加代码？
我有以下代码，这显然是显示两个列表之间并集的标准方法：
union([Head|Tail],List2,Result) :-
member(Head,List2), union(Tail,List2,Result).
union([Head|Tail],List2,[Head|Result]) :-
\+ member(Head,List2), union(Tail,List2,Result).
union([],List2,List2).
并且在以下输入上：
union([a,b,c,d,2,3], [b,c,3,99], Result).
将给出以下输出：
Result = [a,d,2,b,c,3,99] ?
yes
我的问题是，prolog 是如何做到这一点的？ List2 在递归调用中永远不会改变，但最后，它会打印出在两个原始列表之间形成并集的所有元素。
请帮助我理解这段代码。
谢谢。
I have the following code, which is apparently the standard way to show the union between 2 lists:
union([Head|Tail],List2,Result) :-
member(Head,List2), union(Tail,List2,Result).
union([Head|Tail],List2,[Head|Result]) :-
\+ member(Head,List2), union(Tail,List2,Result).
union([],List2,List2).
and on the following input:
union([a,b,c,d,2,3], [b,c,3,99], Result).
will give me the following output:
Result = [a,d,2,b,c,3,99] ?
yes
My question is, How does prolog do this? List2 is never changed throught the recursive calls, but at the end, it prints out all elements that make the union between the 2 original lists.
Please help me understand this code.
Thank you.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
假设您询问 union([1,2],[2],R)。
根据第一条规则， union([1|[2]],[2],R) 为 true，如果
成员(1,[2]) -->错误的
然后 prolog 将检查第二条规则 union([1|[2]],[2],[1|R]) 是否为真
+成员(1,[2]) -->真的
和 union([2],[2],R)
现在， union([2|[]],[2],R) 将为 true（第一条规则）如果
成员(2,[2]) --> true
并且 union([],[2],R)
union([],[2],R) 将为 true（第三条规则），如果 R=[2]
那么 R=[2] ，因此对 union 的第一次调用返回[1|[2]] = [1,2]
一个了解“prolog 是如何实现的”的有用工具是trace/0：
总而言之：List2 没有改变，但谓词也不返回 List2；它返回由 List2 创建的列表和 List1 的唯一元素
let's assume that you ask union([1,2],[2],R).
according to the first rule, union([1|[2]],[2],R) would be true if
member(1,[2]) --> false
then prolog will check the second rule union([1|[2]],[2],[1|R]) will be true if
+member(1,[2]) --> true
and union([2],[2],R)
now, union([2|[]],[2],R) would be true (1st rule) if
member(2,[2]) -->true
and union([],[2],R)
union([],[2],R) would be true (3rd rule) if R=[2]
so R=[2] and therefore the first call to union returns [1|[2]] = [1,2]
a useful tool to find out "how prolog does it" is trace/0:
all in all: List2 doesnt not change but the predicate does not return List2 either; it returns a list created by List2 and the unique elements of List1
这里的算法如下：
1) 将结果初始化为
List2。这部分的实现归功于：2) 遍历
List1并对每个项目执行以下操作：2a) 如果该项目不在
List2中，则将其添加到Result中。该部分的实现要归功于以下子句：2b) 如果该项目位于 List2 中，则不执行任何操作。该部分的实现要归功于以下子句：
要逐步理解序言执行，请参阅@thanosQR答案。
顺便说一句，请注意，此谓词需要设置才能返回良好的并集，否则，
List1中的重复项将在Result中保留重复项（List1中的重复项也会如此） >列表2）。The algorithm in work here is the following :
1) initialize the result to
List2. This part is implemented thanks to :2) go through
List1and do the following for each item :2a) add it to
Resultif the item is not inList2. That part is implemented thanks to this clause :2b) don't do anything if the item is in List2. That part is implemented thanks to this clause :
For step by step comprehension of the prolog execution, please refer to @thanosQR answer.
By the way, note that this predicate needs sets to return a good union, else, a duplicate in
List1will stay a duplicate inResult(so will a duplicate inList2).该代码实际上效率相当低，因此我们不能将其视为计算并集的“标准方法”。乍一看，有两个简单的优化：避免重复成员资格测试，并使用memberchk/2而不是member/2。所以我们可以这样重写：
性能差异巨大。对于相对较小的列表：
我们从 62,532,499 推论传递到 20,002 推论，并且测试不会强制评估所有替代方案（来自成员的回溯点）：添加此我们需要25,015,004更多的推论，尽管没有更多的解决方案可用。这里是来自 SWI-Prolog lists 库的代码：
它与您的版本相似，请注意剪切 (!)
That code it's actually rather inefficient, so we can't assume it as the 'standard way' to compute union. At first glance, there are 2 simple optimizations: avoid repeat the membership test, and use memberchk/2 instead of member/2. So we can rewrite it in the following way:
The difference in performance is huge. With relatively small lists:
we pass from 62,532,499 inferences to 20,002 inferences, and the test doesn't force the evaluation of all alternatives (backtrack points from member): adding this we need 25,015,004 more inferences, albeit no more solution is available. Here the code from SWI-Prolog lists library:
It's similar to your version, please note the cut (!)