Prolog去重函数removeDuplicates中append始终返回false问题排查

首先，你的代码核心问题出在append/3的调用上——append(Head, prevList, List)这一行是错误的！因为append/3的前两个参数都必须是列表，而Head是单个元素（比如a），不是列表结构，这直接导致这个分支永远返回false。

先看你的原代码逻辑：

removeDuplicates([],[]).
removeDuplicates([Head|Tail], List) :- 
    ( member(Head,Tail), removeDuplicates(Tail, prevList), append([], prevList, List) ); 
    ( not(member(Head,Tail)), removeDuplicates(Tail,prevList), append(Head, prevList, List) ).

问题拆解 #

1. 当Head不在Tail中时，你想把Head加到递归结果的前面，但错误地直接传入了单个元素Head给append/3，应该把它包装成单元素列表[Head]才能完成拼接。
2. append([], prevList, List)完全是冗余写法，直接写成List = prevList就可以，空列表和任何列表拼接结果都是原列表，这样更简洁高效。
3. 另外，Prolog规范里变量名建议首字母大写（比如PrevList而非prevList），避免和原子名称混淆。

修正后的基础版本 #

removeDuplicates([], []).
removeDuplicates([Head|Tail], List) :-
    (   member(Head, Tail),
        removeDuplicates(Tail, PrevList),
        List = PrevList
    );
    (   \+ member(Head, Tail),  % 用\+代替not，是更标准的Prolog否定写法
        removeDuplicates(Tail, PrevList),
        append([Head], PrevList, List)
    ).

测试验证 #

现在运行你给出的测试用例：

?- removeDuplicates([a,a,b,c], L).
L = [a, b, c] ;
false.

（这里的false是Prolog回溯尝试寻找其他解时的正常结果，我们的逻辑已经覆盖了所有可能情况）

额外优化建议 #

你当前的实现每次都要遍历Tail检查member，时间复杂度是O(n²)。如果允许调整元素顺序，用累加器记录已出现元素的方式效率更高：

removeDuplicates(List, Result) :-
    removeDuplicates(List, [], Temp),
    reverse(Temp, Result).  % 反转累加器结果，保持原列表顺序

removeDuplicates([], Acc, Acc).
removeDuplicates([Head|Tail], Acc, Result) :-
    member(Head, Acc),
    removeDuplicates(Tail, Acc, Result).
removeDuplicates([Head|Tail], Acc, Result) :-
    \+ member(Head, Acc),
    removeDuplicates(Tail, [Head|Acc], Result).

测试这个优化版：

?- removeDuplicates([a,a,b,c], L).
L = [a, b, c].

这个版本没有多余的回溯结果，整体效率也提升了不少。

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