Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Intersection of two lists of variables

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

like image 614
false Avatar asked Jan 04 '15 01:01

false


1 Answers

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

like image 72
Tudor Berariu Avatar answered Nov 15 '22 10:11

Tudor Berariu