recursion - Prolog 程序中的无效结果

Question

我的程序旨在消除列表中的重复元素。我认为这是正确的。我尝试通过剪切来使其工作，但没有给出正确的结果。

member(X,[X|_]). % If X is Head, it is a member
member(X,[_|T]) :- member(X,T). % If not, Recursively check the tail.

remove_duplicates([],[]).
remove_duplicates([H|T],R):-member(H,T),remove_duplicates(T,R).
remove_duplicates([H|T],[R|REM]):-remove_duplicates(T,REM).

但是我得到了结果:I = [_G2608, _G2611, _G2614|_G2615]对于输入remove_duplicates([a,b,a,b,b,c],I)。

Answer 1

这是一个既纯粹又更高效的版本，因为它只需要恒定的辅助空间。到目前为止发布的解决方案在最坏的情况下需要与第一个参数中列表的大小成比例的空间。但现在来说说正确性:

?- remove_duplicates([A,B], Fs).

我们在这里问:

How must A and B look like to result in a list Fs that has no duplicates?

这个问题不能简单地通过陈述具体的Fs来回答，因为这个Fs可能是[A,B]或 [A] 应该 A 和 B 相同。

?- remove_duplicates([A,B],F).
   A = B, F = [B]
;  F = [A, B], dif(A, B).

这是一个解决方案。此定义需要 another answer 中定义的单调 if_/3 和 memberd_truth/3 .

remove_duplicates([], []).
remove_duplicates([E|Es], Fs0) :-
   if_( memberd_truth(E, Es) , Fs0 = Fs , Fs0 = [E|Fs] ),
   remove_duplicates(Es, Fs).

就我个人而言，我更喜欢一个更相关的名称，例如 list_unique/2 或 list_nub/2 作为暗示 towards Haskell .