Prolog仅删除独特元素

Question

我想返回一个列表,删除所有独特的元素,例如

remUniqueVals([1,1,2,2,3,4,4,5,6,6,6],Q).   
Q = [1,1,2,2,4,4,6,6,6].  

我的问题是,目前我有返回的代码

remUniqueVals([1,1,2,2,3,4,4,5,6,6,6],Q).  
Q = [1, 2, 4, 6, 6].

这样只返回这些非唯一值的第一个实例.这是我的代码:

remUniqueVals([], []).  
remUniqueVals([Q1|RestQ],[Q1|Xs]) :-        
   member(Q1,RestQ),  
   remUniqueVals(RestQ,Xs).  
remUniqueVals([Q1|RestQ],Xs) :-  
   remove(Q1,[Q1|RestQ], NewQ),  
   remUniqueVals(NewQ,Xs).  

我可以看到member(Q1,RestQ)它在第二次检查1,2,4时失败,因为它们现在不再在列表中,因此将它们删除.我想帮助解决这个问题,我的想法是检查member(Q1, PreviousQ),这是决赛中的元素Q.不知道如何实施,虽然任何帮助将不胜感激.

更新:

好的,谢谢你最终的结论:

remUniqueVals(_,[], []).  
remUniqueVals(_,[Q1|RestQ],[Q1|Xs]) :-        
   member(Q1,RestQ), 
   remUniqueVals(Q1,RestQ,Xs).  
remUniqueVals(PrevQ,[Q1|RestQ],[Q1|Xs]) :-        
   Q1 = PrevQ, 
   remUniqueVals(PrevQ,RestQ,Xs).  
remUniqueVals(PrevQ,[_|RestQ],Xs) :-  
   remUniqueVals(PrevQ,RestQ,Xs). 

remUniqueVals(0,[4,1,1,3,2,2,5,5],Q).
Q = [1, 1, 2, 2, 5, 5].

remUniqueVals(0, [A,B,C], [1,1]).
A = 1,
B = 1,
C = 1.

Answer 1

Prolog规则彼此独立地读取,因此对于元素是唯一的而不是元素的情况,需要一个规则.如果元素的顺序不相关,您可以使用:

?- remUniqueVals([A,B,C], [1,1]).
A = B, B = 1,
dif(C, 1) ;
A = C, C = 1,
dif(B, 1),
dif(B, 1) ;
B = C, C = 1,
dif(A, 1),
dif(A, 1) ;
false.

?- remUniqueVals([1,1,2,2,3,4,4,5,6,6,6],Q).
Q = [1, 1, 2, 2, 4, 4, 6, 6, 6] ;
false.

remUniqueVals([], []).
remUniqueVals([Q1|RestQ],[Q1|Xs0]) :-
   memberd(Q1, RestQ),
   phrase(delall(Q1, RestQ, NewQ), Xs0, Xs),
   remUniqueVals(NewQ, Xs).
remUniqueVals([Q1|RestQ],Xs) :-
   maplist(dif(Q1), RestQ),
   remUniqueVals(RestQ,Xs).

memberd(X, [X|_Xs]).
memberd(X, [Y|Xs]) :-
   dif(X,Y),
   memberd(X, Xs).

delall(_X, [], []) --> [].
delall(X, [X|Xs], Ys) -->
   [X],
   delall(X, Xs, Ys).
delall(X, [Y|Xs], [Y|Ys]) -->
   {dif(X,Y)},
   delall(X, Xs, Ys).

这是一个替代定义,使用memberd/2它可能更有效if_/3:

memberd(E, [X|Xs]) :-
   if_(E = X, true, memberd(E, Xs) ).

Answer 2

这与原始解决方案类似,但它会在辅助列表中收集非唯一值并检查它以避免从原始列表中删除最后一个:

remove_uniq_vals(L, R) :-
    remove_uniq_vals(L, [], R).

remove_uniq_vals([], _, []).
remove_uniq_vals([X|T], A, R) :-
    (   member(X, A)
    ->  R = [X|T1], A1 = A
    ;   member(X, T)
    ->  R = [X|T1], A1 = [X|A]
    ;   R = T1, A1 = A
    ),
    remove_uniq_vals(T, A1, T1).

测试...

| ?- remove_uniq_vals([1,2,3,1,2,3,1,2,3,4,3], Q).

Q = [1,2,3,1,2,3,1,2,3,3]

(1 ms) yes
| ?- remove_uniq_vals([1,1,2,2,3,4,4,5,6,6,6], Q).

Q = [1,1,2,2,4,4,6,6,6]

yes

因此,如果第一个参数是输入,则谓词的效果很好,并且它保持列表中其余元素的原始顺序.

然而,该谓词不是完全关系的,因为它将使第一个参数是已知数量的元素的未实例化列表并且第二个参数是不同固定数量的元素的列表的情况失败.所以像这样的东西会起作用:

| ?- remove_uniq_vals([A,B,C], L).

B = A
C = A
L = [A,A,A]

(1 ms) yes

但是类似下面的事情失败了:

| ?- remove_uniq_vals([A,B,C], [1,1]).

no

Answer 3

这是另一个纯粹的关系解决方案,受到@ CapelliC解决方案的启发.现在这个保留了重复的顺序.有趣的是,现在必须明确地完成@CapelliC解决方案中发生的隐式量化.

拥有纯粹的关系定义的最大优点是noes is noes.并且ayes是ayes.那就是:你不必担心你得到的答案是否正确.这是正确的(或不正确 - 但它不是部分正确).非关系解决方案通常可以通过instantiation_error在方法失败的情况下生成来清理.但是你可以自己验证,两者都"忘记"了这样的测试,从而为bug做好了准备.这些其他解决方案的安全测试本来是ground(Xs)或者ground(Xs), acyclic_term(Xs)经常被认为太受限制了.

remUniqueVals2(Xs, Ys) :-
   tfilter(list_withduplicate_truth(Xs),Xs,Ys).

list_withduplicate_truth(L, E, Truth) :-
   phrase(
      (  all(dif(E)),
         (  {Truth = false}
         |  [E],
            all(dif(E)),
            (   {Truth = false}
            |   {Truth = true},
                [E],
                ...
            )
         )
      ),  L).

all(_) --> [].
all(P_1) -->
   [E],
   {call(P_1,E)},
   all(P_1).

... --> [] | [_], ... .

tfilter(     _, [], []).
tfilter(TFilter_2, [E|Es], Fs0) :-
   call(TFilter_2,E,Truth),
   (  Truth = false,
      Fs0 = Fs
   ;  Truth = true,
      Fs0 = [E|Fs]
   ),
   tfilter(TFilter_2, Es, Fs).

另一种更紧凑的使用方式 if_/3

tfilter(   _, [], []).
tfilter(TFilter_2, [E|Es], Fs0) :-
   if_(call(TFilter_2,E), Fs0 = [E|Fs], Fs0 = Fs ),
   tfilter(TFilter_2, Es, Fs).