list - A U B U C的序言联盟

我最近开始学习Prolog，但无法解决如何将三个列表合并的问题。

我能够合并两个列表:

%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的定义

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

这是一种差异显示的情况:

?- union([A],[B],[C,D]).
A = C,
B = D,
dif(C, D).

答案是:它们必须不同。

您的原始版本对此查询失败，但是，对于像以下这样的特殊实例，该版本成功:

?- A = 1, B = 2, union([A],[B],[C,D]).

因此它可以成功实现，但不能对其进行概括。因此，这不是纯粹的逻辑关系。

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

现在排除了不成为成员的选择，这对于某些模式是正确的，例如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] ;
false.

实际上，我们得到了| Arg2 || Arg1 | -1多余的答案。因此，削减有一些充分的理由。
union/3仍然不够高效的另一个原因是，对于(预期的)基本案例，它留下了不必要的选择点。同样，@ TudorBerariu的解决方案没有此问题:

?- union([a],[a],Zs).
Zs = [a] ;    %    <--- Prolog does not know that there is nothing left.
false.

消除冗余

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

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

从右到左读取的递归规则如下:

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

通过具体化引入确定性。

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

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

memberd_t(_X, [], false).
memberd_t(X, [X|_Ys], true).
memberd_t(X, [Y|Ys], Truth) :-
   dif(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).          % 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可以使用不同的真值多次成功(即为true和false都可以是)，但控制构造使If_0仅成功一次(仅适用于true)。
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):
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) ).
关于list - A U B U C的序言联盟，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27358456/

ARG2

list - A U B U C的序言联盟