A U B U C 的 Prolog 联合 [英] Prolog union for A U B U C
问题描述
我最近开始学习Prolog，但我无法解决如何将三个列表合并.
我能够合并 2 个列表:
%元素元素(X，[X|_]).元素(X，[_|Y]):-元素(X，Y).％联盟联合([]，M，M).联合([X|Y]，L，S):-元素(X，L)，联合(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，[]).非成员(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) :- 元素(X,L), union(Y,L,S).^^^^^^^^^^^^^这是一个改进的定义:
成员(X，[X|_Ys]).成员(X，[Y|Ys]):-差异(X，Y)，％新！成员(X，Ys).递归规则，从右到左阅读，如下:
<块引用>假设 memberd(X, Ys) 对于某些 X 和 Ys 已经为真.鉴于此，并且我们有一个合适的 Y，它不同于 X.那么
我们可以得出结论，
memberd(X, [Y|Ys]) 也是真的.所以这消除了多余的解决方案.但是我们的定义仍然不是很有效:它仍然要对每个元素访问 Arg2 两次，然后无法得出没有备选方案的结论.在任何情况下:拒绝切割将其移除.
通过具体化引入确定性.
比较memberd/2和non_member/2的定义.尽管它们描述了彼此的相反"，但它们看起来非常相似:
non_member(_X, []).非成员(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], true).memberd_t(X, [Y|Ys], Truth) :-差异(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], Truth) :-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 可能会以不同的真值成功多次(即，它可以同时为真和假)，但控制构造使 If_0 成功只为真实一次.
if_(If_1, Then_0, Else_0) :-调用(如果_1，T)，( T == true -> 调用(Then_0);T == 假->呼叫(Else_0);非变量(T)->抛出(错误(类型错误(布尔值，T)，_));/* var(T) */throw(error(instantiation_error,_))).=(X，Y，T):-( X == Y -> T = 真;X = Y ->T = 假;T = 真，X = Y;T = 假，差异(X，Y)％ISO扩展% 抛出(错误(实例化错误，_)) % ISO 严格).等于_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，假).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 的 Prolog 联合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
