Intersection of two lists of variables

Question

How to define in ISO Prolog a (meta-logical) predicate for the intersection of two lists of variables that runs in linear time? The variables may appear in any determined order. No implementation dependent property like the "age" of variables must influence the outcome.

In analogy to library(ordsets), let's call the relation 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

That is, the third argument is an output argument, that unifies with the intersection of the first two arguments.

See this list of the built-ins from the current ISO standard (ISO/IEC 13211-1:1995 including Cor.2).

(Note, that I did answer this question in the course of another one several years ago. However, it remains hidden and invisible to Google.)

Answer 1

If term_variables/2 works in a time linear with the size of its first argument, then this might work:

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).

Each common variable appears only once in the result list no matter how many times it appears in the two given lists.

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

Also, it might give strange results as in this case:

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

(permutation/2 might help here).