Пролог: проверка на наличие дубликатов в списке

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, мы можем действовать следующим образом:

Далее мы используем SICStus Prolog 4.3.2:

 : - use_module( библиотека( списки)).

allDistinct(Es):-
   ( земля(Es)
   -> сортировать(Es, Fs),
      same_length(Es, Fs); throw( error( instantiation_error,
                  instantiation_error(allDistinct (Es), 1)))).

Примеры запросов:

|? - allDistinct ([1,2,3]).
да
|?- allDistinct([1,2,3.0]).
да
|? - allDistinct ([1,2, 3.0,2]).нет|? - allDistinct ([1,2,3.0,X]).! Ошибка экземпляра в аргументе 1 пользователя:allDistinct/1! target:  allDistinct([1,2,3.0,_197])

Answer 2

Сказуемое sort/2 сортирует и удаляет дубликаты из списка. Вы можете использовать его, сравнить длину (length/2 предикат) нового отсортированного списка со старым, если они отличаются, были некоторые дублированные значения.

Answer 3

Это один из тех вопросов, с большим количеством альтернативных, разумных решений. Предполагая, что можно использовать предикаты общей библиотеки, вот еще один:

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

Преимущество этого решения в том, что оно прекращает сканирование списка, как только обнаруживает дублированный элемент. Но быстрее ли это решений, основанных на стандарте? sort/2 предикат? Непонятно как sort/2 является высокооптимизированным предикатом в большинстве систем Prolog. Кроме того, давайте не будем забывать, что, если мы не уверены, что все элементы списка связаны, мы должны быть в безопасности и проверить это (см. Ответ @repeat).