AUBUC的Prolog联盟

Question

我最近开始学习Prolog,我无法解决如何组合三个列表的问题.

我能够组合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).

有人可以帮我吗？

Answer 1

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]与[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] ;
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).

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

memberd(X, Ys)对某些人来说X,假设已经是真的了Ys.鉴于此,鉴于我们有一个Y不同的拟合X.然后

我们可以得出结论,这也是memberd(X, [Y|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真正的仅是成功的只有一次.

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

Answer 2

您可以将前两个列表的并集,然后是该结果与第三个列表之间的并集:

union(L1, L2, L3, U):-union(L1, L2, U12), union(U12, L3, U).

您可以union/3使用剪切操作符进行改进:

union([],M,M).
union([X|Y],L,S) :- element(X,L), !, union(Y,L,S).
union([X|Y],L,[X|S]) :- union(Y,L,S).