确定逻辑程序

Question

目标是执行谓词noDupl/2。

该谓词的第一个参数是要分析的列表，第二个参数是不重复的数字列表。

我不明白下面的代码，当我编译它，它给了一个错误消息contained是不确定的过程，但作为提示，它是写，我们可以为预定义的谓语contained和notContained使用。我想我需要定义contained和notContained。

noDupl(XS, Res):- 
    help(XS, [],Res). 

help([],_,[]). 
help([X|XS],Seen,[X|Res]):- 
    notContained(X,XS), 
    notContained(X,Seen), 
    help(XS, [X|Seen], Res). 
help([X|XS],Seen,Res):- 
    contained(X,Seen), 
    help(XS, Seen, Res). 
help([X|XS],Seen,Res):- 
    contained(X,XS), 
    help(XS, [X|Seen], Res). 

有人可以请解释我的问题。

Answer 1

丢失的定义可能是：

contained(X,[X|_]). 
contained(X,[E|Es]) :- 
    dif(X, E), 
    contained(X, Es). 

notContained(_X, []). 
notContained(X, [E|Es]) :- 
    dif(X, E), 
    notContained(X, Es). 

（我喜欢叫这些关系而memberd/2和non_member/2）

你给我的定义扩展与认为这样的元素一个额外的参数的关系远。

要理解每个子句的含义，请按箭头方向从右到左读取（:-是1970年代的ASCII代码←）。让我们的第一条规则：

提供的，X不是XS的元素，
提供的，X不是Seen的元素，
提供的，help(X, [X|Seen], Res)是真实的，

---

那么也 help([X|XS],Seen,[X|Res])是正确的。

换句话说，如果X既不在走访元素Seen也不尚未访问XS元素的列表中，那么它不具备重复。

有些难以理解的是，你给出的子句是否相互排斥 - 严格来说，这不是你关心的问题，只要你只对声明性属性感兴趣，但这是一个好主意以避免这种冗余。

这里有一个情况下，如果这种冗余表明：

?- noDupl([a,a,a],U). 
U = [] ; 
U = [] ; 
false. 

理想情况下，系统会给出一个确定的答案：

?- noDupl([a,a,a], U). 
U = []. 

就个人而言，我不喜欢很多东西分成太多的情况下。基本上，我们可以有两个：它是一个重复的，它是没有的。

可以提供一个正确的定义，并且仍然可以完全确定确定性是可能的情况 - 例如当第一个参数是“充分实例化”（其中包括一个地面列表）时。我们来看看这个方向是否有一些答案。

Answer 2

我注释你的代码为您提供：

noDupl(XS , Res) :- % Res is the [unique] set of element from the bag XS 
    help(XS, [],Res) % if invoking the helper succeeds. 
    .     % 

help([]  , _ , []  ) . % the empty list is unique. 
help([X|XS] , Seen , [X|Res]) :- % A non-empty list is unique, if... 
    notContained(X,XS),    % - its head (X) is not contained in its tail (XS), and 
    notContained(X,Seen),   % - X has not already been seen, and 
    help(XS, [X|Seen], Res).  % - the remainder of the list is unique. 
help([X|XS] , Seen , Res) :-  % otherwise... 
    contained(X,Seen) ,    % - if X has been seen, 
    help(XS, Seen, Res).   % - we discard it and recurse down on the tail. 
help([X|XS],Seen,Res):-   % otherwise... 
    contained(X,XS),    % - if X is in the tail of the source list, 
    help(XS, [X|Seen], Res).  % - we discard it (but add it to 'seen'). 

你contained/2和notContained/2`谓词可能被定义为这样：

contained(X , [X|_] ) :- ! . 
contained(X , [Y|Ys]) :- X \= Y , contained(X , Ys) . 

not_contained(_ , []) . 
not_contained(X , [Y|Ys]) :- X \= Y , not_contained(X,Ys) . 

现在，我可能会丢失的东西你代码，但是它有很多冗余。你可以简单地写这样的事情（使用内建member/2和reverse/2）：

no_dupes(List , Unique) :- no_dupes(Bag , [] , Set) . 

no_dupes([] , V , S) .  % if we've exhausted the bag, the list of visited items is our set (in reverse order of the source) 
    reverse(V,S)    % - reverset it 
    .       % - to put our set in source order 
no_dupes([X|Xs] , V , S) :- % otherwise ... 
    (member(X,V) ->   % - if X is already in the set, 
    V1 = V     % - then we discard X 
    ; V1 = [X|V]    % - else we add X to the set 
) ,       % And... 
    no_dupes(Xs , V1 , S)  % we recurse down on the remainder 
    .       % Easy! 

Answer 3

可这在纯净和高效的方式来完成？ 是，通过使用 tpartition/4和(=)/3像这样：

dups_gone([] ,[]). 
dups_gone([X|Xs],Zs0) :- 
    tpartition(=(X),Xs,Ts,Fs), 
    if_(Ts=[], Zs0=[X|Zs], Zs0=Zs), 
    dups_gone(Fs,Zs). 

一些样品地查询（所有这些成功的确定性）：

?- dups_gone([a,a,a],Xs). 
Xs = []. 

?- dups_gone([a,b,c],Xs). 
Xs = [a, b, c]. 

?- dups_gone([a,b,c,b],Xs). 
Xs = [a, c]. 

?- dups_gone([a,b,c,b,a],Xs). 
Xs = [c]. 

?- dups_gone([a,b,c,b,a,a,a],Xs). 
Xs = [c]. 

?- dups_gone([a,b,c,b,a,a,a,c],Xs). 
Xs = []. 

这也适用于更广泛的查询。考虑：

?- length(Xs,N), dups_gone(Xs,Zs). 
    N = 0, Xs = [],   Zs = [] 
; N = 1, Xs = [_A],   Zs = [_A] 
; N = 2, Xs = [_A,_A],  Zs = [] 
; N = 2, Xs = [_A,_B],  Zs = [_A,_B], dif(_A,_B) 
; N = 3, Xs = [_A,_A,_A], Zs = [] 
; N = 3, Xs = [_A,_A,_B], Zs = [_B],  dif(_A,_B) 
; N = 3, Xs = [_A,_B,_A], Zs = [_B],  dif(_A,_B) 
; N = 3, Xs = [_B,_A,_A], Zs = [_B],  dif(_A,_B), dif(_A,_B) 
; N = 3, Xs = [_A,_B,_C], Zs = [_A,_B,_C], dif(_A,_B), dif(_A,_C), dif(_B,_C) 
; N = 4, Xs = [_A,_A,_A,_A], Zs = [] 
...