找到条件下的最小列表

Question

在 SWI-Prolog 中，我想从两个列表 L1 和 L2 中建立列表 L，其中元素数最少条件，即 1 ∈ L1 和 1 ∈ L2。如果 1 ∉ L1 和 1 ∈ L2，则 L = L1。如果 1 ∈ L1 和 1 ∉ L2，则 L = L2。如果 1 ∉ L1 和 1 ∉ L2，则谓词 returns 为假。

我可以在 Prolog 中使用以下条件对此进行评估：

minset_one(D1, D2, T) :- ((member(1, D1), not(member(1, D2))) -> T=D1).
minset_one(D1, D2, T) :- ((not(member(1, D1)), member(1, D2)) -> T=D2).
minset_one(D1, D2, T) :- (member(1, D1), member(1, D2), length(D1,L1), length(D2,L2), L1 >= L2) -> T=D2.
minset_one(D1, D2, T) :- (member(1, D1), member(1, D2), length(D1,L1), length(D2,L2), L2 > L1) -> T=D1.

我对那个函数的问题是，经常调用成员函数。他们是一种以这种方式降低谓词复杂性的方法吗，函数

member(1, D1)
member(1, D2)
length(D1, L1)
length(D2, L2)

只调用一次？

Answer 1

我认为您可以使用包装器/辅助谓词来完成这些检查，然后查找一些固定答案：

% minset_one(1 in D1, 1 in D2, D1, D2, D1Len, D2Len, T).
minset_one_(true,  false, D1, _,  _,     _,     D1).
minset_one_(false, true,  _,  D2, _,     _,     D2).
minset_one_(true,  true,  _,  D2, D1Len, D2Len, D2) :- D1Len >= D2Len.
minset_one_(true,  true,  D1, _,  D1Len, D2Len, D1) :- D1Len < D2Len.

minset_one(D1, D2, T) :-
    (member(1, D1) -> D1check = true ; D1check = false),
    (member(1, D2) -> D2check = true ; D2check = false),
    length(D1, D1Len),
    length(D2, D2Len),
    
    minset_one_(D1check, D2check, D1, D2, D1Len, D2Len, T).

Answer 2

当 minset_one/3 的参数未充分实例化时，您的代码和 lose logical-purity 中的代码：

?- D1 = [X,Y,Z], D2 = [U,V], minset_one(D1,D2,T).
   D1 = [1,Y,Z], D2 = [1,V], T = D2
;  false.                           % no more solutions!

这显然不完整。还有其他解决方案。我们输了 logical-purity.

那么，我们能做些什么呢？基本上，我们有两个选择：

预先检查 D1、D2 和 T，并在实例化不充分时抛出 instantiation_error。
使用更适合保留 logical-purity.

在这个答案中，我想展示如何实现第二个选项。

代码基于if_/3 which is the core of library(reif)。简而言之，我们将关系的真值具体化，并对这些值使用 Prolog 索引。

使用 SWI-Prolog 8.4.2:

?- use_module(library(reif)).

首先，shorter_than_t(Xs,Ys,T) 将 "list Xs 短于 Ys" 修改为 T:

shorter_than_t([],Ys,T) :-
   aux_nil_shorter_than(Ys,T).
shorter_than_t([_|Xs],Ys,T) :-
   aux_cons_shorter_than_t(Ys,Xs,T).

aux_nil_shorter_than_t([],false).
aux_nil_shorter_than_t([_|_],true).

aux_cons_shorter_than_t([],_,false).
aux_cons_shorter_than_t([_|Ys],Xs,T) :-
   shorter_than_t(Xs,Ys,T).

基于shorter_than_t/3我们定义minset_one/3:

minset_one(D1,D2,T) :-
   if_(shorter_than_t(D1,D2),
       if_(memberd_t(1,D1), D1=T, (memberd_t(1,D2,true),D2=T)),
       if_(memberd_t(1,D2), D2=T, (memberd_t(1,D1,true),D1=T))).

现在让我们运行再次查询上面的内容：

?- D1 = [X,Y,Z], D2 = [U,V], minset_one(D1,D2,T).
   D1 = [X,Y,Z], D2 = [1,V], T = D2
;  D1 = [X,Y,Z], D2 = [U,1], T = D2, dif(U,1)
;  D1 = [1,Y,Z], D2 = [U,V], T = D1, dif(U,1), dif(V,1)
;  D1 = [X,1,Z], D2 = [U,V], T = D1, dif(U,1), dif(V,1), dif(X,1)
;  D1 = [X,Y,1], D2 = [U,V], T = D1, dif(U,1), dif(V,1), dif(X,1), dif(Y,1)
;  false.

终于，minset_one/3完成了！

找到条件下的最小列表

Find smallest list under conditions

prolog

member

min