list - 在 Prolog 中删除重复项并保持顺序

Question

我正在尝试创建一个谓词，从列表中删除重复项，同时保持其相对顺序。例如，列表 [1,2,2,3,4,5,5,2] 应返回 [1,2,3,4,5]。但是，我的代码只能删除连续的重复项，例如不能删除末尾的 2。

remove_duplicates([],[]).
remove_duplicates([H],[H]).
remove_duplicates([H,H|T],[H|List]) :- remove_duplicates(T,List).
remove_duplicates([H,X|T],[H|T1]):- X\=H, remove_duplicates([X|T],T1).

我想到的另一种方法是使用 member 来查看 Tail 是否包含 Head。然而，我能想到的解决这个问题的唯一方法是，如果头是尾部的成员，我将删除头部。然而，这将仅保留数字的最后一个实例，并破坏列表中数字的相对顺序。

例如:

[1,2,2,3,4,5,5,2] 
[1,3,4,5,2]

当我真正想要的时候

[1,2,3,4,5]

Answer 1

您可以使用累加器:一个额外的参数，这里的列表最初为空，当新元素出现时将会增长。每次递归调用都会传递列表(或更新的副本)。

例如:

remove_duplicates(LA, LB) :-
    remove_duplicates(LA, LB, <b>[]</b>).

remove_duplicates([], [], <b>_</b>).
remove_duplicates([H|T], R, <b>Seen</b>) :-
    (  member(H, Seen)
    -> (R = S, <b>Seen1 = Seen</b>)
    ;  (R = [H|S], <b>Seen1 = [H|Seen]</b>)
    ),
    remove_duplicates(T, S, <b>Seen1</b>).

这给了我们:

?- remove_duplicates([1,2,2,3,4,5,5,2], L).
L = [1, 2, 3, 4, 5].

当然，您可以使用比列表更有效的数据结构。我把它留作练习。