两个变量列表的交集

Question

如何在ISO Prolog中定义一个(元逻辑)谓词,用于在线性时间内运行的两个变量列表的交集？变量可以按任何确定的顺序出现.没有像变量"年龄"这样的实现依赖属性必须影响结果.

与之类似library(ordsets),我们称之为关系varset_intersection(As, Bs, As_cap_Bs).

?- varset_intersection([A,B], [C,D], []).
true.

?-varset_intersection([A,B], [B,A], []).
false.

?- varset_intersection([A,B,C], [C,A,D], Inter).
Inter = [A,C].
or
Inter = [C,A].

?- varset_intersection([A,B],[A,B],[A,C]).
B = C
or
A = B, A = C

?- varset_intersection([A,B,C],[A,B],[A,C]).
idem

也就是说,第三个参数是输出参数,它与前两个参数的交集相结合.

请参阅当前ISO标准(ISO/IEC 13211-1:1995,包括Cor.2)的内置插件列表.

(请注意,几年前我在另一个问题中回答了这个问题.然而,谷歌仍然隐藏着这个问题.)

Answer 1

如果term_variables/2工作时间与其第一个参数的大小成线性关系，那么这可能会工作：

varset_intersection(As, Bs, As_cap_Bs):-
    term_variables([As, Bs], As_and_Bs),
    term_variables(As, SetAs),
    append(SetAs, OnlyBs, As_and_Bs),
    term_variables([OnlyBs, Bs], SetBs),
    append(OnlyBs, As_cap_Bs, SetBs).

每个公共变量在结果列表中只出现一次，无论它在两个给定列表中出现多少次。

?- varset_intersection2([A,_C,A,A,A], [A,_B,A,A,A], L).
L = [A].

此外，它可能会产生奇怪的结果，如下例所示：

?- varset_intersection([A,_X,B,C], [B,C,_Y,A], [C, A, B]).
A = B, B = C.

（permutation/2这里可能有帮助）。