Prolog：去除重复项

Question

我正在尝试从prolog列表中删除重复条目。因此，一个列表[a，b，a，c，b，a]将返回[a，b，c]。我不能使用任何内置函数。在这里搜索后，我找到了以下代码。

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

但是这会将我的列表转换成[c,b,a]而不是[a,b,c]

我已经删除了一个代码，它将取一个元素和一个列表，并返回一个在列表中该元素出现次数已被删除的列表。因此，我试图将其合并到我的去重方法中，但我并不真正了解Prolog，所以它没有起作用。从逻辑上讲，我想取一个列表，用新列表减去所有头部出现次数的递归调用来连接头部。这就是SML中代码的样子。

fun remv(_,nil) = nil
|   remv(a,x::xs) = if x=a then remv(a,xs) else x::remv(a,xs);
fun remvdub (nil) = nil
|   remvdub(x::xs) = x::remvdub(remv(x,xs)); 

这是我在Prolog中尝试的内容。

remv(_,[],[]).
remv(X,[X|T],Ans) :- remv(X,T,Ans).
remv(X,[H|T],[H|K]) :- remv(X,T,K). 

remvdub([],[]).
remvdub([H|T],[H|Ans]) :- remvdub(Ans1,Ans), remv(H,T,Ans1).

我错过了什么？

- user3043403

Answer 1

% An empty list is a set.
set([], []).

% Put the head in the result,
% remove all occurrences of the head from the tail,
% make a set out of that.
set([H|T], [H|T1]) :- 
    remv(H, T, T2),
    set(T2, T1).

% Removing anything from an empty list yields an empty list.
remv(_, [], []).

% If the head is the element we want to remove,
% do not keep the head and
% remove the element from the tail to get the new list.
remv(X, [X|T], T1) :- remv(X, T, T1).

% If the head is NOT the element we want to remove,
% keep the head and
% remove the element from the tail to get the new tail.
remv(X, [H|T], [H|T1]) :-
    X \= H,
    remv(X, T, T1).

- SQB

---

谢谢SQB，这正是我想要做的逻辑。即使我查看了你的代码，我似乎也找不到我的错误在哪里，它们对我来说看起来都一样。但是你的代码可以运行，而我的则陷入了无限循环。 - user3043403

嗯，我想我弄明白了。在“-”内的顺序很重要，所以我的代码应该是：remvdub([H|T],[H|Ans]) :- remv(H,T,Ans1), remvdub(Ans1,Ans)。 - user3043403

Answer 2

您发布的Prolog代码片段在逻辑上是正确的。如果您想保留每个重复项目的第一个副本，而不是最后一个副本，则可以按照以下方式更改代码：

member(X,[X|_]) :- !.
member(X,[_|T]) :- member(X,T).
set(A,B) :- set(A, B, []).
set([],[],_).
set([H|T],[H|Out],Seen) :- not(member(H,Seen)), set(T,Out, [H|Seen]).
set([H|T],Out, Seen) :- member(H,Seen), set(T,Out,Seen).

这个想法是添加第三个参数，代表你已经看过的项目列表，并根据它来检查成员身份，而不是根据剩余列表来检查成员身份。请注意，set/2用于隐藏谓词用户不需要关注的第三个参数。

在ideone上的演示。

- Sergey Kalinichenko

---

谢谢dasblinkenlight，它起作用了！出于好奇，是否有一种方法可以在代码底部尝试的方式中执行操作？在那里，我使用删除代码来插入逐渐变小的列表，并删除头和头的重复项？ - user3043403

@user3043403 我不理解sml，所以我无法理解工作原型代码。然而，remvdub/2谓词的第二个子句看起来非常可疑，因为它似乎会进入无限递归。 - Sergey Kalinichenko