Prolog中不使用内置谓词实现列表去重并保持顺序的问题

问题描述 #

我是Prolog新手，希望实现列表去重并保持原有顺序。思路是将列表拆分为Head|Tail，使用累加器递归处理：判断头部元素是否在累加器中，若是则不做处理，若否则将头部元素加入累加器。

写出的代码如下：

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

remove_duplicates(List, Set) :- help_remove_duplicate(List, [], Set).

help_remove_duplicate([], Acc, Acc). 

help_remove_duplicate([H|T], Acc, Set) :- 
   is_member(H, A),
   help_remove_duplicate(T, Acc, Set).

help_remove_duplicate([H|T], Acc, Set) :- 
   help_remove_duplicate(T, [H|Acc], Set).

上述代码能实现去重，但会打乱原有顺序，输入[1,2,3,4,4,4,5]会返回[5,4,3,2,1]。

问题原因 #

代码中每次将新元素H插入到累加器Acc的头部（[H|Acc]），递归结束后累加器里的元素顺序是原列表的逆序，直接返回Acc就会得到倒序结果。另外代码里还存在笔误：is_member(H, A)中的A是未定义变量，应该改为Acc。

修复方案 #

方法1：反转累加器（高效推荐）

修改递归的终止条件，将最终的累加器反转后返回，就能恢复原顺序。同时修正笔误，并添加否定判断避免重复解：

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

remove_duplicates(List, Set) :- help_remove_duplicate(List, [], Set).

% 终止时反转累加器，恢复原顺序
help_remove_duplicate([], Acc, Set) :- reverse(Acc, Set).

help_remove_duplicate([H|T], Acc, Set) :- 
   is_member(H, Acc),
   help_remove_duplicate(T, Acc, Set).

% 仅当元素不在累加器中时，才加入累加器头部
help_remove_duplicate([H|T], Acc, Set) :- 
   \+ is_member(H, Acc),
   help_remove_duplicate(T, [H|Acc], Set).

测试输入remove_duplicates([1,2,3,4,4,4,5], S).，会得到S = [1,2,3,4,5]，符合预期。

方法2：保持累加器顺序（直观但效率较低）

如果不想反转，可以在添加新元素时将其追加到累加器的尾部，这样累加器始终保持原顺序。但每次append操作需要遍历整个累加器，长列表下效率不如方法1：

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

remove_duplicates(List, Set) :- help_remove_duplicate(List, [], Set).

help_remove_duplicate([], Acc, Acc).

help_remove_duplicate([H|T], Acc, Set) :- 
   is_member(H, Acc),
   help_remove_duplicate(T, Acc, Set).

help_remove_duplicate([H|T], Acc, Set) :- 
   \+ is_member(H, Acc),
   append(Acc, [H], NewAcc),
   help_remove_duplicate(T, NewAcc, Set).

内容的提问来源于stack exchange，提问作者at-at