A U B U C的Prolog工会 [英] Prolog union for A U B U C

问题描述

我最近开始学习Prolog，但我无法解决如何将三个列表结合在一起的情况.

I've started to learn Prolog recently and I can't solve how to make union of three lists.

我能够合并2个列表:

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

有人可以帮我吗?

推荐答案

union(A, B, C, U) :-
   union(A, B, V),
   union(C, V, U).

您可以通过替换来改进union/3的定义

Your definition of union/3 can be improved by replacing

... not(element(X,L)), ...

作者

... maplist(dif(X),L), ...

或

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

[A]和[B]如何看起来像它们的并集包含2个元素?

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.

那么dif/2一切都很好吗?不幸的是没有. @TudorBerariu有充分的理由要减薪，因为它反映了我们对这种关系的某些意图.削减有效地反映了两个关键意图

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

• 现在排除了不成为成员的选择，这对于某些模式是正确的，例如Arg1和Arg2都是足够实例化的术语.一个安全的近似值是地面术语.

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

无需查看Arg2列表中的其他元素，这同样只有在Arg1和Arg2被充分实例化的情况下才成立.

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

OP的定义和上面的定义的缺点在于，两者的含义都过于笼统，可以通过Arg2中的重复元素来观察:

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.

实际上，我们获得了| Arg2 | ^{| Arg1 |} -1的冗余答案.因此，削减有一些充分的理由.

In fact, we get |Arg2|^|Arg1|-1 redundant answers. So the cut had some good reason to be there.

union/3仍然不是很有效的另一个原因是，对于(预期的)地面案例，它留下了不必要的选择点.同样，@ TudorBerariu的解决方案不存在此问题:

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.

消除冗余

那么多冗余答案的真正罪魁祸首是第一条规则. element(a,[a,a])(通常称为member/2)将成功两次.

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

以下是改进的定义:

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:

对于某些X和Ys，

假定memberd(X, Ys)已经成立.鉴于此，并且我们有一个与X不同的拟合Y.然后

---

我们可以得出结论，memberd(X, [Y|Ys])也是正确的.

Assume memberd(X, Ys) is true already for some X and Ys. Given that, and given that we have a fitting Y which is different from X. Then

---

we can conclude that also memberd(X, [Y|Ys]) is true.

因此，这消除了冗余解决方案.但是我们的定义仍然不是很有效:它仍然必须为每个元素两次访问Arg2，然后无法断定没有其他选择.无论如何:拒绝放置切口以删除该切口.

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.

比较memberd/2和non_member/2的定义.尽管它们彼此描述为相反"，但它们看起来非常相似:

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

递归规则是相同的！唯一的事实是不同的事实.让我们将它们合并为一个定义-带有一个附加参数，告诉我们是指memberd(true)还是non_member(false):

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

请注意if_(If_1, Then_0, Else_0)和if-then-else控制构造( If_0 -> Then_0 ; Else_0 )之间的区别.尽管If_1可能会以不同的真值成功执行多次(也就是说，它可以都是是非)，但是控制构造只能使If_0成功一次，因为它仅是true.

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

为确保memberd_t/3始终从第一参数索引中受益，请使用以下定义(感谢@WillNess):

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屋！