A U B U C 的序言联合 [英] Prolog union for A U B U C
问题描述
最近开始学习Prolog，解决不了三个列表的并集问题.
我能够合并 2 个列表:
%element元素(X，[X|_]).元素(X,[_|Y]):-元素(X，Y).％联盟联合([]，M，M).union([X|Y],L,S) :- 元素(X,L),union(Y,L,S).union([X|Y],L,[X|S]) :- (not(element(X,L))),union(Y,L,S).有人可以帮我吗?
union(A, B, C, U) :-联合(A，B，V)，联合(C，V，U).你对union/3的定义可以通过替换来改进
... not(element(X,L)), ...由
... maplist(dif(X),L), ...或
... non_member(X, L), ....非成员(_X，[]).non_member(X, [E|Es]) :-差异(X，E)，非成员(X，Es).以下是显示差异的情况:
?- union([A],[B],[C,D]).A = C,B = D,差异(C，D).<块引用>
[A] 和 [B] 的联合包含 2 个元素应该怎样?
答案是:它们必须不同.
您的原始版本在此查询中失败，但是，它在以下特殊实例中成功:
?- A = 1, B = 2, union([A],[B],[C,D]).所以它成功了，但它的泛化失败了.因此，它不是纯粹的逻辑关系.
那么 dif/2 一切都好吗?不幸的是没有.@TudorBerariu 有充分的理由削减，因为它反映了我们对这种关系的一些意图.剪裁有效地反映了两个关键意图
现在排除了不是成员的选择，这对于某些模式是正确的，例如 Arg1 和 Arg2 都是充分实例化的术语.一个安全的近似值是基本术语.
不需要查看列表 Arg2 中的其他元素，这同样只有在 Arg1 和 Arg2 被充分实例化时才成立.
问题仅在术语未充分实例化时显示..
OP 的定义和上面的定义的缺点是，两者都不必要地过于笼统，这可以通过 Arg2 中的重复元素观察到:
?- union([a,a],[a,a],Zs).Zs = [a, a] ;Zs = [a, a] ;Zs = [a, a] ;Zs = [a, a] ;错误的.事实上，我们得到了|Arg2||Arg1|-1 个多余的答案.所以剪辑有一些很好的理由.
union/3 目前效率不高的另一个原因是，对于(预期的)地面情况，它留下了不必要的选择点.同样，@TudorBerariu 的解决方案没有这个问题:
?- union([a],[a],Zs).Zs = [a] ;% <--- Prolog 不知道什么都没有了.错误的.消除冗余
造成这么多冗余答案的真正罪魁祸首是第一条规则.element(a,[a,a])(通常称为member/2)会成功两次.
union([X|Y],L,S) :- element(X,L), union(Y,L,S).^^^^^^^^^^^^^这是一个改进的定义:
memberd(X, [X|_Ys]).成员(X, [Y|Ys]) :-差异(X，Y)，％新！成员(X，Ys).递归规则，从右到左阅读，内容如下:
<块引用>假设 memberd(X, Ys) 对于某些 X 和 Ys 已经成立.鉴于此，并且鉴于我们有一个与 X 不同的拟合 Y.然后
我们可以得出结论，
memberd(X, [Y|Ys]) 也是正确的.所以这消除了多余的解决方案.但是我们的定义仍然不是很有效:它仍然需要为每个元素访问 Arg2 两次，然后无法得出没有替代方案的结论.在任何情况下:拒绝放置切口来移除它.
通过具体化引入决定论.
比较memberd/2 和non_member/2 的定义.尽管它们描述了彼此的相反"，但它们看起来非常相似:
non_member(_X, []).non_member(X, [Y|Ys]) :-差异(X，Y)，非成员(X，Ys).成员(X，[X|_Ys]).成员(X, [Y|Ys]) :-差异(X，Y)，成员(X，Ys).递归规则是一样的！只是事实不同而已.让我们将它们合并为一个定义——用一个额外的参数告诉我们是指 memberd (true) 还是 non_member (false>):
memberd_t(_X, [], false).memberd_t(X, [X|_Ys], 真).memberd_t(X, [Y|Ys], 真相) :-差异(X，Y)，memberd_t(X, Ys, Truth).现在，我们的定义变得更紧凑了:
unionp([], Ys, Ys).unionp([X|Xs], Ys, Zs0) :-if_( memberd_t(X, Ys), Zs0 = Zs, Zs0 = [X|Zs] ),unionp(Xs, Ys, Zs).memberd_t(_X, [], false).％ 见下文memberd_t(X, [Y|Ys], 真相) :-if_( X = Y, Truth=true, memberd_t(X, Ys, Truth) ).注意 if_(If_1, Then_0, Else_0) 和 if-then-else 控制结构 ( If_0 -> Then_0 ; Else_0 ) 之间的区别.虽然 If_1 可能会以不同的真值成功多次(也就是说，它可以是 both true 和 false)，但控制结构使 If_0 成功只有一次是真的.
if_(If_1, Then_0, Else_0) :-呼叫(If_1，T)，( T == true -> call(Then_0);T == 假 ->呼叫(Else_0);非变量(T)->抛出(错误(类型错误(布尔，T)，_));/* var(T) */throw(error(instantiation_error,_))).=(X，Y，T):-( X == Y -> T = true;X = Y ->T = 假;T = 真，X = Y;T = 假，dif(X, Y) % ISO 扩展% throw(error(instantiation_error,_)) % ISO 严格).equal_t(X, Y, T) :-=(X，Y，T).为了确保 memberd_t/3 始终从第一个参数索引中受益，而是使用以下定义(感谢 @WillNess):
memberd_t(E, Xs, T) :-i_memberd_t(Xs, E, T).i_memberd_t([], _E, false).i_memberd_t([X|Xs], E, T) :-if_( X = E, T = true, i_memberd_t(Xs, E, T) ).I've started to learn Prolog recently and I can't solve how to make union of three lists.
I was able to make union of 2 lists :
%element
element(X,[X|_]).
element(X,[_|Y]):-
element(X,Y).
%union
union([],M,M).
union([X|Y],L,S) :- element(X,L),union(Y,L,S).
union([X|Y],L,[X|S]) :- (not(element(X,L))),union(Y,L,S).
can anybody help me please ?
union(A, B, C, U) :-
union(A, B, V),
union(C, V, U).
Your definition of union/3 can be improved by replacing
... not(element(X,L)), ...
by
... maplist(dif(X),L), ...
or
... non_member(X, L), ....
non_member(_X, []).
non_member(X, [E|Es]) :-
dif(X, E),
non_member(X, Es).
Here is a case where the difference shows:
?- union([A],[B],[C,D]).
A = C,
B = D,
dif(C, D).
How must
[A]and[B]look like such that their union contains 2 elements?
The answer is: they must be different.
Your original version fails for this query, yet, it succeeds for a specialized instance like:
?- A = 1, B = 2, union([A],[B],[C,D]).
So it succeeds for this, but fails for a generalization of it. Therefore it is not a pure, logical relation.
So is everything fine and perfect with dif/2? Unfortunately not. @TudorBerariu has good reason to go for a cut, since it reflects some of the intention we have about the relation. The cut effectively reflects two key intentions
that the alternative of not being a member is now excluded, which is true for certain modes, like Arg1 and Arg2 being both sufficiently instantiated terms. A safe approximation would be ground terms.
that there is no need to look at further elements in the list Arg2, which again is only true if Arg1 and Arg2 are sufficiently instantiated.
Problems only show when terms are not sufficiently instantiated..
The drawback of OP's definition and the one above, is that both are unnecessarily too general which can be observed with repeated elements in Arg2:
?- union([a,a],[a,a],Zs).
Zs = [a, a] ;
Zs = [a, a] ;
Zs = [a, a] ;
Zs = [a, a] ;
false.
In fact, we get |Arg2||Arg1|-1 redundant answers. So the cut had some good reason to be there.
Another reason why union/3 as it stands is not very efficient is that for the (intended) ground case it leaves open unnecessary choice points. Again, @TudorBerariu's solution does not have this problem:
?- union([a],[a],Zs).
Zs = [a] ; % <--- Prolog does not know that there is nothing left.
false.
Eliminating redundancy
The actual culprit for that many redundant answers is the first rule. element(a,[a,a]) (commonly called member/2) will succeed twice.
union([X|Y],L,S) :- element(X,L), union(Y,L,S).
^^^^^^^^^^^^
Here is an improved definition:
memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
dif(X,Y), % new!
memberd(X, Ys).
The recursive rule, reading it right-to-left, reads as follows:
Assume
memberd(X, Ys)is true already for someXandYs. Given that, and given that we have a fittingYwhich is different fromX. Then
we can conclude that alsomemberd(X, [Y|Ys])is true.
So this has eliminated the redundant solutions. But our definition is still not very efficient: it still has to visit Arg2 twice for each element, and then it is unable to conclude that no alternatives are left. In any case: resist to place a cut to remove this.
Introducing determinism via reification.
Compare the definitions of memberd/2 and non_member/2. Although they describe "the opposite" of each other, they look very similar:
non_member(_X, []).
non_member(X, [Y|Ys]) :-
dif(X,Y),
non_member(X, Ys).
memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
dif(X,Y),
memberd(X, Ys).
The recursive rule is the same! Only the fact is a different one. Let's merge them into one definition - with an additional argument telling whether we mean memberd (true) or non_member (false):
memberd_t(_X, [], false).
memberd_t(X, [X|_Ys], true).
memberd_t(X, [Y|Ys], Truth) :-
dif(X, Y),
memberd_t(X, Ys, Truth).
Now, our definition gets a bit more compact:
unionp([], Ys, Ys).
unionp([X|Xs], Ys, Zs0) :-
if_( memberd_t(X, Ys), Zs0 = Zs, Zs0 = [X|Zs] ),
unionp(Xs, Ys, Zs).
memberd_t(_X, [], false). % see below
memberd_t(X, [Y|Ys], Truth) :-
if_( X = Y, Truth=true, memberd_t(X, Ys, Truth) ).
Note the difference between if_(If_1, Then_0, Else_0) and the if-then-else control construct ( If_0 -> Then_0 ; Else_0 ). While If_1 may succeed several times with different truth values (that is, it can be both true and false), the control construct makes If_0 succeed only once for being true only.
if_(If_1, Then_0, Else_0) :-
call(If_1, T),
( T == true -> call(Then_0)
; T == false -> call(Else_0)
; nonvar(T) -> throw(error(type_error(boolean,T),_))
; /* var(T) */ throw(error(instantiation_error,_))
).
=(X, Y, T) :-
( X == Y -> T = true
; X = Y -> T = false
; T = true, X = Y
; T = false,
dif(X, Y) % ISO extension
% throw(error(instantiation_error,_)) % ISO strict
).
equal_t(X, Y, T) :-
=(X, Y, T).
To ensure that memberd_t/3 will always profit from first-argument indexing, rather use the following definition (thanks to @WillNess):
memberd_t(E, Xs, T) :-
i_memberd_t(Xs, E, T).
i_memberd_t([], _E, false).
i_memberd_t([X|Xs], E, T) :-
if_( X = E, T = true, i_memberd_t(Xs, E, T) ).
这篇关于A U B U C 的序言联合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
