刪除重複連續從列表中的Prolog

Question

我有類似名單如下：

[a,b,b,e,e,f,f,g] 

第一和最後一個條目是單一的，而所有其他被重複。我怎樣才能刪除這些額外的條目。我不應該打擾這個命令。

我嘗試以下，但它得到一個空列表：

removeDups([], []). 
removeDups([H1,H2|T], Newlist) :- 
    (H1 == H2 -> removeDups([H2|T],Newlist) 
    ; removeDups(T,Newlist)). 

?- removeDups([a,b,b,c,c,d,d,e],L). 
L = []. 

編輯：我已經檢查過很多類似的問題上計算器。但在我的清單中，重複是連續的，因此可能有更簡單的解決方案。我無法找到刪除連續重複條目的問題。

Answer 1

在您的謂詞中，第二個參數應始終表示從第一個參數中刪除重複項的結果。這導致當分解成每一種情況下具備以下條款：

remove_dups([], []). % Empty list is empty list with dups removed 
remove_dups([X], [X]). % Single element list is itself with dups removed 

% The result of removing duplicates from `[X,X|T]` should be the same 
% as the result of removing duplicates from `[X|T]` 
remove_dups([X,X|T], [X|R]) :- 
    remove_dups([X|T], [X|R]). 

% The result of removing duplicates from `[X,Y|T]` where X and Y are different 
% should be the result [X|R] where R is the result of removing duplicates 
% from [Y|T] 
remove_dups([X,Y|T], [X|R]) :- 
    X \== Y, 
    remove_dups([Y|T], R). 

第3和第4條款可以被替換爲：

remove_dups([X,Y|T], [X|R]) :- 
    ( X == Y 
    -> remove_dups([Y|T], [X|R]) 
    ; remove_dups([Y|T], R) 
    ). 

但後來其中第一個參數是可變的，它會限制解決方案。

Answer 2

刪除重複項的空列表當然仍然是一個空列表。

如果尾巴不是以頭部開始，我們應該保持頭部。重複刪除的尾部是刪除重複部分的尾部。
這包括尾部爲空的情況（因此它是單元素列表）。

如果列表確實從頭開始重複，我們保持頭部。那麼我們包括頭部時刪除其他重複，因爲頭可能會重複多次。如果我們不包括頭部，我們不能檢查它的尾巴。

remove_dups([],[]). 

remove_dups([H|T], [H|T1]) :- 
    T \= [H|_], 
    remove_dups(T, T1). 

remove_dups([H,H|T], L) :- 
    remove_dups([H|T], L). 

而這裏是an example using SWISh。

Answer 3

爲什麼訴諸於只能在特定情況下使用的解決方案，並在其他情況下產生錯誤的結果？命令式編程是如此1980 ... 80年代很酷，我知道，但也有點有限， 不是？

請試着根據的關係，可以在所有方向使用！

下面是一個使用if_/3對於一般性的解決方案：

 
no_consecutive_duplicates([], []). 
no_consecutive_duplicates([L|Ls0], Ls) :- 
     no_dups(Ls0, L, Ls). 

no_dups([], E, [E]). 
no_dups([L|Ls0], E, Ls) :- 
     if_(L=E, Ls=Ls1, Ls=[E|Ls1]), 
     no_dups(Ls0, L, Ls1). 

它的工作原理也是最常見的情況：

 
?- no_consecutive_duplicates(Ls0, Ls). 
Ls = Ls0, Ls0 = [] 
Ls = Ls0, Ls0 = [_G501] ; 
Ls = [_G501], 
Ls0 = [_G501, _G501] ; 
Ls = [_G501], 
Ls0 = [_G501, _G501, _G501] . 

對於公平枚舉，使用例如：

 
?- length(Ls0, _), no_consecutive_duplicates(Ls0, Ls). 
Ls = Ls0, Ls0 = [] ; 
Ls = Ls0, Ls0 = [_G501] ; 
Ls = [_G501], 
Ls0 = [_G501, _G501] ; 
Ls = [_G775, _G775], 
Ls0 = [_G787, _G775], 
dif(_G775, _G787) . 

注意使用prolog-dif以聲明狀態說明兩個詞是  不同。

順便說一下， 「正常」 的情況下，工作太：

 
?- no_consecutive_duplicates([a,b,c], Ls). 
Ls = [a,b,c]. 

?- no_consecutive_duplicates([a,a,b,c,c], Ls). 
Ls = [a,b,c]. 

注意，這兩個查詢成功確定性。

這不是很好，我們可以概括這一點，並檢查也稍微複雜的情況？

 
?- no_consecutive_duplicates([a,b,X], Ls). 
Ls = [a, b], 
X = b ; 
Ls = [a, b, X], 
dif(X, b). 

保持純粹的人！