list 删除列表中的重复项（Prolog）

Remove duplicates in list (Prolog)

提问by evgeniuz

I am completely new to Prolog and trying some exercises. One of them is:

我对 Prolog 完全陌生并尝试了一些练习。其中之一是：

Write a predicate set(InList,OutList) which takes as input an arbitrary list, and returns a list in which each element of the input list appears only once.

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

Here is my solution:

这是我的解决方案：

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

I'm not allowed to use any of built-in predicates (It would be better even do not use not/1). The problem is, that set/2gives multiple samesolutions. The more repetitions in the input list, the more solutions will result. What am I doing wrong? Thanks in advance.

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

采纳答案by Tim

You are getting multiple solutions due to Prolog's backtracking. Technically, each solution provided is correct, which is why it is being generated. If you want just one solution to be generated, you are going to have to stop backtracking at some point. This is what the Prolog cutis used for. You might find that reading up on that will help you with this problem.

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

Update: Right. Your member()predicate is evaluating as truein several different ways if the first variable is in multiple positions in the second variable.

更新：没错。如果第一个变量在第二个变量中的多个位置，则您的member()谓词true以几种不同的方式进行评估。

I've used the name mymember()for this predicate, so as not to conflict with GNU Prolog's builtin member()predicate. My knowledge base now looks like this:

我使用了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).

So, mymember(1, [1, 1, 1]).evaluates as truein three different ways:

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

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

true ? a

true

true

no

If you want to have only one answer, you're going to have to use a cut. Changing the first definition of mymember()to this:

如果你只想得到一个答案，你将不得不使用削减。将第一个定义更改为mymember()：

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

Solves your problem.

解决您的问题。

Furthermore, you can avoid not()altogether, if you wish, by defining a notamember()predicate yourself. The choice is yours.

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

回答by repeat

You are on the right track... Stay pure---it's easy!

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

Use reified equality predicates =/3and dif/3in combination with if_/3, as implemented in Prolog union for A U B U C:

使用具体化的相等谓词=/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 ).

Based on these predicates we build a reified membership predicate list_item_isMember/3. It is semantically equivalent with memberd_truth/3by @false. We rearrange the argument order so the list is the 1st argument. This enables first-argumentindexing which prevents leaving useless choice-points behind as memberd_truth/3would create.

基于这些谓词，我们构建了一个具体化的成员资格谓词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).

A simple query shows that all redundant answers have been eliminatedand that the goal succeeds without leaving any choice-points behind:

一个简单的查询表明，所有多余的答案都已消除，目标成功而没有留下任何选择点：

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

---

---

Edit 2015-04-23

编辑 2015-04-23

I was inspired by @Ludwig's answer of set/2, which goes like this:

我受到@Ludwig 对 的回答的启发set/2，它是这样的：

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

SWI-Prolog's builtin predicate subtract/3can be non-monotone, which may restrict its use. list_item_subtracted/3is a monotonevariant of it:

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/2is like set/2, but is based on list_item_subtracted/3---not subtract/3:

list_setB/2就像set/2，但基于list_item_subtracted/3---not subtract/3：

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

The following queries compare list_set/2and list_setB/2:

以下查询比较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

回答by sumx

A simpler (and likely faster) solution is to use library predicate sort/2 which remove duplicates in O(n log n). Definitely works in Yap prolog and SWIPL

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

回答by Ludwig

I think that a better way to do this would be:

我认为更好的方法是：

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

So, for example ?- set([1,4,1,1,3,4],S)give you as output:

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

S = [1, 4, 3]

回答by kjo

Adding my answer to this old thread:

将我的答案添加到这个旧线程中：

notmember(_,[]).
notmember(X,[H|T]):-X\=H,notmember(X,T).

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

The only virtueof this solution is that it uses only those predicates that have been introduced by the point where this exercise appears in the original text.

这个解决方案的唯一优点是它只使用了在原始文本中出现这个练习的地方引入的那些谓词。

回答by Chiranjeet Maity

/* Remove duplicates from a list without accumulator */
our_member(A,[A|Rest]).
our_member(A, [_|Rest]):-
    our_member(A, Rest).

remove_dup([],[]):-!.
remove_dup([X|Rest],L):-
    our_member(X,Rest),!,
    remove_dup(Rest,L).
remove_dup([X|Rest],[X|L]):-
    remove_dup(Rest,L).

回答by Anna

You just have to stop the backtracking of Prolog.

你只需要停止 Prolog 的回溯。

enter code here
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).

回答by RobotMan

Using the support function mymemberof Tim, you can do this if the order of elements in the set isn't important:

使用mymemberTim的支持函数，如果集合中元素的顺序不重要，您可以这样做：

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

mkset([],[]).
mkset([T|C], S) :- mymember(T,C),!, mkset(C,S).
mkset([T|C], S) :- mkset(C,Z), S=[T|Z].

So, for example ?- mkset([1,4,1,1,3,4],S)give you as output:

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

S = [1, 3, 4]

but, if you want a set with the elements ordered like in the list you can use:

但是，如果您想要一个按照列表中元素排序的集合，您可以使用：

mkset2([],[], _).
mkset2([T|C], S, D) :- mkset2(C,Z,[T|D]), ((mymember(T,D), S=Z,!) ; S=[T|Z]).
mkset(L, S) :- mkset2(L,S,[]).

This solution, with the same input of the previous example, give to you:

此解决方案与上一个示例的输入相同，为您提供：

S = [1, 4, 3]

This time the elements are in the same order as they appear in the input list.

这次元素的顺序与它们出现在输入列表中的顺序相同。

回答by Michele Mendel

This works without cut, but it needs more lines and another argument. If I change the [H2|T2] to S on line three, it will produce multiple results. I don't understand why.

这无需剪切即可工作，但它需要更多的线条和另一个参数。如果我将第三行的 [H2|T2] 更改为 S，则会产生多个结果。我不明白为什么。

setb([],[],_).
setb([H|T],[H|T2],A) :- not(member(H,A)),setb(T,T2,[H|A]).
setb([H|T],[H2|T2],A) :- member(H,A),setb(T,[H2|T2],A).
setb([H|T],[],A) :- member(H,A),setb(T,[],A).
set(L,S) :- setb(L,S,[]).