確定邏輯程序

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 = [] 
...