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([], []).
remove_duplicates([H|T], R) :-
  (   memberchk(H,T)
  ->  remove_duplicates(T, R)
  ;   remove_duplicates(T, R0), 
      R = [H|R0]
  ).

像这样的显式条件不会创建虚假的选择点。正是这个选择点导致 Tudor 的解决方案需要一个否定的 member/2，而您正试图通过削减来纠正它。因此，尽管它看起来不那么漂亮，但它是一种更有效的解决方案。

此外，使用 memberchk/2 而不是 member/2 是对不需要 member/2 生成解决方案的能力的情况的小优化。比较：

?- time(remove_duplicates([a,b,a,b,b,c], I)).
% 14 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 1037114 Lips)
I = [a, b, c].

Tudor 对您的代码的修订：

?- time(remove_duplicates([a,b,a,b,b,c], I)).
% 28 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 2264822 Lips)
I = [a, b, c] ;
% 28 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 1338752 Lips)
I = [a, b, c] ;
% 15 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 1065341 Lips)
false.

Answer 2

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

?- 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.

Prolog 程序中的无效结果

Invalid Result in Prolog Program

recursion

prolog