2つの変数リストの交差

Question

で実行される2つの変数リストの交差のためのISO Prolog述語をどのように定義するか時間？変数は、任意の決定された順序で現れることができる。変数の「年齢」のような実装依存のプロパティは、結果に影響する必要がありません。 library(ordsets)と同様に

は、のは、3番目の引数は最初の二つの引数の交差点で統一した出力引数、で、ある関係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を含む）のlist of the built-insを参照してください。

（私は1つ、数年前に別の過程でこの質問に答えるなかったことに注意してください、しかし、それはGoogleに隠された目に見えないままになります。）

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

各共通変数は関係なく、それがどのように表示されるかを何回結果リストに一度だけ表示されません2つの与えられたリスト。

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

（permutation/2ここでは役立つかもしれない）：

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

また、この場合のように奇妙な結果を与えるかもしれません。

Answer 2

unify_with_occurs_check(Var, ListOfVars)が失敗した場合や、一定時間内に成功した場合は、この実装がすべき線形時間での収量の答え：

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

この実装は、与えられたリストは重複が含まれているときに問題があります。

?- 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] ; 

編集：下記のコメントの@falseの観測のおかげで、手動で書き込まれたフィルタに変更されました。bagof/3

Answer 3

可能な解決策は、Bloom filterを使用することです。衝突の場合、結果は間違っている可能性がありますが、より良い衝突抵抗を持つ関数が存在します。ここには、単一のハッシュ関数を使用する実装があります。

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

私はfoldl/4とinclude/3はISOでないことを知っているが、その実装が容易です。

Answer 4

copy_term/2は線形時間を使用している場合、私は次のような作品を信じて：

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

アイデアは、最初のコピーの変数を接地し、それらの間の共有変数を保持するためにcopy_term/2に1回の呼び出しで両方のリストをコピーすることです第2のコピーの接地された位置に対応する第2のリストの元の変数を取り出す。