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

编辑：我已经在 stackoverflow 上检查过很多类似的问题。但在我的列表中，重复项是连续的，因此可能有更简单的解决方案。我找不到有关删除连续重复条目的问题。

Answer 1

为什么要采用只能在非常特定的情况下使用的解决方案，而在其他情况下会产生错误的结果？命令式编程太 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] 。

对于 fair 枚举，请使用例如：

？- 长度（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],
差异（X，b）。

保持纯洁！

Answer 2

在谓词中，第二个参数应始终表示从第一个参数中删除重复项的结果。分解为每种情况后，就会产生以下子句：

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 3

删除重复项后的空列表当然仍然是空列表。

如果尾巴不是从头开始的，我们应该保留头。去重尾部是去除重复项的尾部。
这包括尾部为空的情况（因此它是单元素列表）。

如果列表确实以重复的头部开始，我们保留头部。然后，我们在删除其他重复项时“包含”头部，因为头部可能会重复多次。如果我们不包括头部，我们就无法检查尾部。

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

这是 

使用 SWISh 的示例

。

Answer 4

takeout(X,[X|R],R).
takeout(X,[F|Fs],[F|S]):- takeout(X,Fs,S).
/*takeout function used to remove
 delete given element from the list*/


rem([X],[X]).
rem([H|T],Z):- member(H,T) , takeout(H,[H|T],L) ,!, rem(L,Z).
rem([H|T],[H|Z]):- \+member(H,T) , rem(T,Z).

/* I used cut to stop backtracking of takeout function
 rem([X],[X]). when only one elem present return the same list
 rem([H|T],Z):-member(H,T) , takeout(H,[H|T],L) ,!, rem(L,Z).
 used to takeout the duplicate element from the list.
 rem([H|T],[H|Z]):- \+member(H,T) , rem(T,Z).
 if Head is not present in the tail , do nothing and check for the same in tail.
 */