prolog - 如何从 SWI-Prolog 的列表中删除重复项？

Question

我需要编写一个谓词remove_duplicates/2来删除给定列表中的重复元素。例如:

？- 删除重复项([a，a，b，c，c]，列表)。列表 = [a,b,c] 是

请记住，我只学习了两天的SWI-Prolog，只了解Prolog的基础知识。这就是我现在所拥有的:

remove_duplicates([H | T], List) :- 成员(H, T), 追加(T, [], List1)。

这适用于列表[a,a,b,c]，但不适用于尾部两个元素相同的列表。我想我必须以某种方式将 Head 删除到临时列表中，创建一个新的 Head，然后重复谓词。我不知道该怎么做。另外，当 Head 不在 Tail 中时，例如使用 [a,b,b,c] 之类的列表，终端只会显示 False，因为 member(H, T) 不正确。

有什么想法吗？

Answer 1

要删除重复项，如果顺序无关紧要，最简单的方法是使用 sort/2:

?- sort([a,a,b,b,c], X).
X = [a, b, c].

?- sort([c,c,a,a,b], X).
X = [a, b, c].

当然，您会看到元素的原始顺序丢失了。更重要的是，只有当您正在排序的列表已经被磨碎(其中没有自由变量)时，这才保证正确。考虑这个小例子:

?- sort([X,Y], [a,a]).
X = Y, Y = a.

如果您的目标是删除重复项，感觉不太正确......

所以你不妨这样写:

must_be(ground, List), sort(List, Unique).

您也可以自己做，并保持原来的顺序。但是，您需要记录到目前为止所看到的元素。例如，您可以将它们保留在额外列表中:

The list of element seen so far is empty at the beginning

list_unique(List, Unique) :-
    list_unique_1(List, [], Us).

list_unique_1([], _, []).
list_unique_1([X|Xs], So_far, Us) :-
    list_unique_2(X, Xs, So_far, Us).

If all the elements seen so far are different from X, put it in the list of unique elements and add it to the list of elements seen so far.

list_unique_2(X, Xs, So_far, [X|Us]) :-
    maplist(dif(X), So_far),
    list_unique_1(Xs, [X|So_far], Us).

If the element has been seen so far, just skip it.

list_unique_2(X, Xs, So_far, Us) :-
    memberchk(X, So_far),
    list_unique_1(Xs, So_far, Us).

这是最直接的方法。还有其他更聪明的方法可以做到这一点，可能具有更好的复杂性，但这是最容易编写的。