6

如何在 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 标准（包括Cor.2的 ISO/IEC 13211-1:1995 ）的内置列表。

（请注意，我确实在几年前的另一个问题中回答了这个问题。但是，它对谷歌来说仍然是隐藏和不可见的。）

4

4 回答 4

3

如果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可能在这里有所帮助）。

于 2015-01-04T16:05:16.797 回答
2

如果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以保留它们之间的共享变量，然后将第一个副本的变量接地，然后挑选出与第二个副本的接地位置相对应的第二个列表的原始变量。

于 2015-04-03T13:31:54.603 回答
1

如果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] ;

已编辑：bagof/3由于@false 在下面的评论中的观察，更改为手动编写的过滤器。

于 2015-01-04T11:13:51.850 回答
0

一种可能的解决方案是使用布隆过滤器。如果发生碰撞，结果可能是错误的，但存在更好的抗碰撞功能。这是一个使用单个哈希函数的实现。

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，但它们的实施很容易。

于 2015-01-04T12:49:22.047 回答