Intersection of two lists of variables

Question

How to define a (metalogical) predicate in ISO Prolog for the intersection of two lists of variables that work in linear time? Variables can be displayed in any specific order. No implementation-dependent property, such as the "age" of variables, should affect the result.

Similar to library(ordsets) , call the 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 the output argument, which is combined with the intersection of the first two arguments.

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

(Please note that I answered this question a few years ago, but 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, 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 list of results, no matter how many times it appears in two lists.

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

In addition, it can 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 may help here).

Answer 2

If copy_term/2 uses linear time, I believe the following works:

 varset_intersection(As, Bs, Cs) :- copy_term(As-Bs, CopyAs-CopyBs), ground_list(CopyAs), select_grounded(CopyBs, Bs, Cs). ground_list([]). ground_list([a|Xs]) :- ground_list(Xs). select_grounded([], [], []). select_grounded([X|Xs], [_|Bs], Cs) :- var(X), !, select_grounded(Xs, Bs, Cs). select_grounded([_|Xs], [B|Bs], [B|Cs]) :- select_grounded(Xs, Bs, Cs). 

The idea is to copy both lists in one call to copy_term/2 to save the common variables between them, then ground the variables of the first copy, then select the source variables of the second list corresponding to the grounded positions of the second copy.

Answer 3

If unify_with_occurs_check(Var, ListOfVars) fails or succeeds in constant time, this implementation should give answers in linear time:

 filter_vars([], _, Acc, Acc). filter_vars([A|As], Bs, Acc, As_cap_Bs):- ( \+ unify_with_occurs_check(A, Bs) -> filter_vars(As, Bs, [A|Acc], As_cap_Bs) ; filter_vars(As, Bs, Acc, As_cap_Bs) ). varset_intersection(As, Bs, As_cap_Bs):- filter_vars(As, Bs, [], Inter), permutation(Inter, As_cap_Bs). 

There are problems in this implementation when the specified lists contain duplicates:

 ?- varset_intersection1([A,A,A,A,B], [B,A], L). L = [B, A, A, A, A] ; ?- varset_intersection1([B,A], [A,A,A,A,B], L). L = [A, B] ; 

Edited: bagof/3 changed to a hand-written filter due to @false observation in the comments below.

Answer 4

A possible solution is to use a Bloom filter . In the event of a collision, the result may be incorrect, but there are functions with better resistance to collision. Here is an implementation that uses one hash function.

 sum_codes([], _, Sum, Sum). sum_codes([Head|Tail], K, Acc,Sum):- Acc1 is Head * (256 ** K) + Acc, K1 is (K + 1) mod 4, sum_codes(Tail, K1, Acc1, Sum). hash_func(Var, HashValue):- with_output_to(atom(A), write(Var)), atom_codes(A, Codes), sum_codes(Codes, 0, 0, Sum), HashValue is Sum mod 1024. add_to_bitarray(Var, BAIn, BAOut):- hash_func(Var, HashValue), BAOut is BAIn \/ (1 << HashValue). bitarray_contains(BA, Var):- hash_func(Var, HashValue), R is BA /\ (1 << HashValue), R > 0. varset_intersection(As, Bs, As_cap_Bs):- foldl(add_to_bitarray, As, 0, BA), include(bitarray_contains(BA), Bs, As_cap_Bs). 

I know that foldl/4 and include/3 are not ISO, but their implementation is simple.