list - Prolog：检查列表中的重复项

Question

1. 编写一个谓词allDistinct/1，其参数是（符号的）列表，如果列表中的所有符号都不同，则该谓词成功。

   notin(A,[]).
   notin(A,[B|C]) :-
      A\=B,
      notin(A,C).
   
   allDistinct([]).
   allDistinct([_]).
   allDistinct([A|B]) :-
      notin(A,B), 
      allDistinct(B).
   

Answer 1

跟进@whd之前的草图，我们可以这样进行。

基于此，iwhen/2我们可以简洁地定义distinct/1如下：

:- use_module(library(lists), [same_length/2]).

distinct(Es) :-
   iwhen(ground(Es), (sort(Es,Fs),same_length(Es,Fs))).

使用 SICStus Prolog 4.5.0 的示例查询：

| ?- 不同的（[1,2,3]）。
是的
| ?- 不同的（[1,2,3.0]）。
是的
| ?- 不同的（[1,2,3.0,2]）。
不
| ?- 不同的（[1,2,3.0,X]）。
！错误（实例化_错误，_283）

Answer 2

谓词sort/2排序并从列表中删除重复项。您可以使用它，将新排序列表的长度（length/2谓词）与旧排序列表进行比较，如果它们不同，则存在一些重复值。

Answer 3

这是具有相当数量的替代合理解决方案的问题之一。假设可以使用常见的库谓词，这里还有一个：

all_distinct(List) :-
    \+ (
        select(Element, List, Tail),
        select(Element, Tail, _)
    ).

此解决方案的一个性能优势是它会在找到重复元素后立即停止扫描列表。但它是否比基于标准sort/2谓词的解决方案更快？Unclear assort/2是大多数 Prolog 系统中高度优化的谓词。另外，我们不要忘记，除非我们确定所有列表元素都已绑定，否则我们应该安全并检查它（请参阅@repeat 答案）。