删除列表中的重复项(Prolog)

Question

我是Prolog的新手,并尝试了一些练习.其中之一是:

编写一个谓词集(InList,OutList),它将任意列表作为输入,并返回一个列表,其中输入列表的每个元素只出现一次.

这是我的解决方案:

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

set([],[]).
set([H|T],[H|Out]) :-
    not(member(H,T)),
    set(T,Out).
set([H|T],Out) :-
    member(H,T),
    set(T,Out).

我不允许使用任何内置谓词(即使不使用也会更好not/1).问题是,这set/2给出了多个相同的解决方案.输入列表中的重复次数越多,解决方案就越多.我究竟做错了什么？提前致谢.

Answer 1

由于Prolog的回溯,您将获得多种解决方案.从技术上讲,提供的每个解决方案都是正确的,这就是生成它的原因.如果您只想生成一个解决方案,那么您将不得不在某个时刻停止回溯.这就是Prolog 剪切用于的目的.你可能会发现阅读它会帮助你解决这个问题.

更新:对.您的member()谓词评估为true几种不同的方式,如果第一个变量是在第二个变量的多个位置.

我已经使用了mymember()这个谓词的名称,以免与GNU Prolog的内置member()谓词发生冲突.我的知识库现在看起来像这样:

mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).

not(A) :- \+ call(A).

set([],[]).
set([H|T],[H|Out]) :-
    not(mymember(H,T)),
    set(T,Out).
set([H|T],Out) :-
    mymember(H,T),
    set(T,Out).

因此,以三种不同的方式mymember(1, [1, 1, 1]).进行评估true:

| ?- mymember(1, [1, 1, 1]).

true ? a

true

true

no

如果你只想要一个答案,你将不得不使用一个剪辑.将第一个定义更改为mymember():

mymember(X,[X|_]) :- !.

解决你的问题.

此外,not()如果您愿意,您可以通过notamember()自己定义谓词来完全避免.这是你的选择.

Answer 2

你走在正确的轨道上...... 保持纯洁 - 这很容易!

使用具体的等式谓词=/3并dif/3结合使用if_/3,如AUBUC的Prolog union中所实现的:

=(X, Y, R) :- X == Y,    !, R = true.
=(X, Y, R) :- ?=(X, Y),  !, R = false. % syntactically different
=(X, Y, R) :- X \= Y,    !, R = false. % semantically different
=(X, Y, R) :- R == true, !, X = Y.
=(X, X, true).
=(X, Y, false) :-
   dif(X, Y).

% dif/3 is defined like (=)/3
dif(X, Y, R) :- X == Y,    !, R = false.
dif(X, Y, R) :- ?=(X, Y),  !, R = true. % syntactically different
dif(X, Y, R) :- X \= Y,    !, R = true. % semantically different
dif(X, Y, R) :- R == true, !, X \= Y.
dif(X, Y, true) :-         % succeed first!
   dif(X, Y).
dif(X, X, false).

if_(C_1, Then_0, Else_0) :-
   call(C_1, Truth),
   functor(Truth,_,0),  % safety check
   ( Truth == true -> Then_0 ; Truth == false, Else_0 ).

基于这些谓词,我们构建了一个具体化的成员谓词list_item_isMember/3.它在语义上等同于memberd_truth/3@false.我们重新排列参数顺序,因此列表是第一个参数.这使得第一个参数索引能够防止将无用的选择点留在后面memberd_truth/3.

list_item_isMember([],_,false).
list_item_isMember([X|Xs],E,Truth) :-
   if_(E = X, Truth = true, list_item_isMember(Xs,E,Truth)).

list_set([],[]).
list_set([X|Xs],Ys) :-
    if_(list_item_isMember(Xs,X), Ys = Ys0, Ys = [X|Ys0]),
    list_set(Xs,Ys0).

一个简单的查询显示所有多余的答案都已消除,并且目标成功而不会留下任何选择点:

?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs).
Xs = [4,3,2,1].                         % succeeds deterministically

编辑2015-04-23

我被@Ludwig的答案所启发set/2,其答案如下:

set([],[]).
set([H|T],[H|T1]) :- subtract(T,[H],T2), set(T2,T1).

SWI-Prolog的内置谓词subtract/3可以是非单调的,这可能会限制其使用.list_item_subtracted/3是它的单调变体:

list_item_subtracted([],_,[]).
list_item_subtracted([A|As],E,Bs1) :-
    if_(dif(A,E), Bs1 = [A|Bs], Bs = Bs1),
    list_item_subtracted(As,E,Bs).

list_setB/2就像set/2,但是基于list_item_subtracted/3---不是subtract/3:

list_setB([],[]).
list_setB([X|Xs1],[X|Ys]) :-
    list_item_subtracted(Xs1,X,Xs),
    list_setB(Xs,Ys).

以下查询比较list_set/2和list_setB/2:

?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1], Xs).
Xs = [4,3,2,1].                          % succeeds deterministically
?- list_setB([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs).
Xs = [1,2,3,4].                          % succeeds deterministically

?- list_set(Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b] 
...                                      % does not terminate universally
?- list_setB(Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b]
...                                      % does not terminate universally

Answer 3

一个更简单(也可能更快)的解决方案是使用库谓词sort/2来删除O(n log n)中的重复项.绝对适用于Yap prolog和SWIPL

Answer 4

我认为更好的方法是：

set([], []).
set([H|T], [H|T1]) :- subtract(T, [H], T2), set(T2, T1).

所以，例如?- set([1,4,1,1,3,4],S)给你作为输出：

S = [1, 4, 3]