Пролог: Первое дублирующее значение

Question

Мне нужно найти первое дублирующее значение в списке.

prep(3,[1,3,5,3,5]). Должно быть правдой.

prep(5,[1,3,5,3,5]). Должно быть ложным.

Я думал проверить равенство с текущим значением и предыдущими членами списка до тех пор, пока не найду дубликат, если он найдет один, который будет проверять на равенство с X, но я не знаю, как это сделать в Prolog!

Я ценю любую помощь! Спасибо

Answer 1

Не уверен, что это домашнее задание/существуют ограничения на то, какие предикаты вы можете использовать, но это дает пролог, чтобы сделать рекурсию для вас.

В нем говорится: найдите все дубликаты, т.е. где есть элемент с индексом списка I1, а другой с I2, так что они оба имеют одно и то же значение N, а индексы не совпадают, т. е. не учитывать тот же элемент списка, что и дубликат.

Эти дубликаты помещаются (в порядке их нахождения, с самого начала в решающем порядке) в списке AllDups, и предикат является истинным, если первый дубликат найден слиянием с M, значением, которое вы проверяете.

Первая попытка: Это работает, но это очень неэффективно, строительство список всех дублей

prep(M, List) :- 
    findall(N, 
     (nth0(I1, List, N), 
     nth0(I2, List, N), 
     not(I1 =:= I2)), 
     AllDups), 
    nth1(1, AllDups, M). 


?- prep(3,[1,3,5,3,5]). 
true. 

?- prep(5,[1,3,5,3,5]). 
false. 

Даже если вы не можете использовать FindAll, это может помочь вам решить, как это сделать " вручную'.

Вторая попытка: Это не работает/откатывается слишком далеко уступая ложноположительный

Вы даже можете сделать это без FindAll - использовать nth0 найти первый элемент дубликат, а затем, если это унифицирует с значение, которое вы проверяете, оно возвращает true, иначе false.

prep(N, List) :- 
     nth0(I1, List, N), 
     nth0(I2, List, N), 
     not(I1 =:= I2). 

Третья попытка: Это работает, и возвращается, как только первый дубликат был найден

prep(M, List) :- 
     nth0(I1, List, N), 
     nth0(I2, List, N), 
     not(I1 =:= I2), !, 
     M == N. 

Answer 2

представитель (N, список): - добавить (L1, [N | _] , список), добавьте (_, [N | _], L1), \ + (Rep (_, L1)).

Answer 3

Вот чистая версия, использующая dif/2, которая реализует звуковое неравенство. dif/2 предлагается B-Prolog, YAP-Prolog, SICStus-Prolog и SWI-Prolog.

 
firstdup(E, [E|L]) :- 
    member(E, L). 
firstdup(E, [N|L]) :- 
    non_member(N, L), 
    firstdup(E, L). 

member(E, [E|_L]). 
member(E, [_X|L]) :- 
    member(E, L). 

non_member(_E, []). 
non_member(E, [F|Fs]) :- 
    dif(E, F), 
    non_member(E, Fs). 

Преимущества, что он также может быть использован с более общих запросов:

 
?- firstdup(E, [A,B,C]). 
E = A, A = B ; 
E = A, A = C ; 
E = C, 
B = C, 
dif(A, C) ; 
false. 

Здесь мы получаем три ответа: A является дубликатом в первых двух ответов, но на двух разных основаниях : A может быть B или C. В третьем ответе B является дубликатом, но это будет только дубликат, если C отличается от A.

Чтобы понять определение, читайте :- как стрелка ← Так что с правой стороны то, что вы знаете, а слева - то, что вы заключаете. Часто в начале немного раздражает читать предикаты в этом направлении, ведь вы, возможно, соблазнитесь следовать «потоку исполнения». Но часто эта нить ведет в никуда –, она становится слишком сложной для понимания.

Первое правило гласит:

условие E является элементом списка L мы приходим к выводу, что [E|L] имеет E в качестве первого дубликата.

Второе правило гласит:

условие E является первым дубликатом L (не паникуйте здесь и сказать, что мы не знаем, что ...) и при условии, что N не является элементом L мы приходим к выводу, что [N|L] имеет E как первый дубликат.

Предикат member/2 предоставляется во многих системах Prolog и nonmember(X,L) может быть определен как maplist(dif(X),L). Таким образом, можно было бы определить firstdup/2 скорее как:

 
firstdup(E, [E|L]) :- 
    member(E, L). 
firstdup(E, [N|L]) :- 
    maplist(dif(N), L), 
    firstdup(E, L). 

Answer 4

В этом ответе мы улучшить логически чистый код, представленный в this earlier answer. Шаг за шагом:

1. Мы объединяем два предиката memberd/2 и non_member/2 к одному, memberd_t/3, который использует дополнительный аргумент для материализации членов списка в истинностное значение (true или false).

   memberd_t/3 эквивалентно memberd/2 + non_member/2, поэтому мы могли определить так:

    
   memberd_t(X,Xs,true) :- 
       memberd(X,Xs). 
   memberd_t(X,Xs,false) :- 
       non_member(X,Xs). 
   

   Или, наоборот, мы могли определить memberd/2 и non_member/2 так:

    
   memberd(X,Xs) :- 
       memberd_t(X,Xs,true). 
   
   non_member(X,Xs) :- 
       memberd_t(X,Xs,false). 
   

   На практике мы используем настроенную реализацию memberd_t/3 -one w с лучшим детерминизмом.

   Давайте посмотрим, что memberd_t/3 фактически охватывает как memberd/2иnon_member/2!

    
   ?- memberd_t(X,[1,2,3],T). 
       T = true ,  X=1 
   ; T = true ,    X=2 
   ; T = true ,       X=3 
   ; T = false, dif(X,1), dif(X,2), dif(X,3). 
   

2. Возьмите следующий вариант предиката firstdup/2 (defined earlier) в качестве отправной точки:

    
   firstdup(E,[X|Xs]) :- 
       ( memberd(X,Xs), 
        E=X  
       ; non_member(X,Xs), 
        firstdup(E,Xs) 
       ). 
   

3. Давайте заменить использование memberd/2 и non_member/2 с memberd_t/3!

    
   firstdup(E,[X|Xs]) :- 
       ( memberd_t(X,Xs,true), 
        E=X 
       ; memberd_t(X,Xs,false), 
        firstdup(E,Xs) 
       ). 
   

4. Давайте тали memberd_t/3!

    
   firstdup(E,[X|Xs]) :- 
       memberd_t(X,Xs,T), 
       ( T=true 
       -> E=X  
       ; T=false, 
        firstdup(E,Xs) 
       ). 
   

5. Над рисунком pred_t(OtherArgs,T), (T = true -> Then ; T = false, Else) могут быть выражены более сжато с использованием if_/3, написание if_(pred_t(OtherArgs),Then,Else).

    
   firstdup(E,[X|Xs]) :- 
       if_(memberd_t(X,Xs), 
        E=X, 
        firstdup(E,Xs)). 
   

---

Давайте рассмотрим некоторые вопросы!

 
?- firstdup(1,[1,2,3,1]). 
true.        % succeeds deterministically 

?- firstdup(X,[1,2,3,1]). 
X = 1.        % succeeds deterministically 

?- firstdup(X,[A,B,C]).    % succeeds, leaving behind a choicepoint 
     A=X ,  B=X     % ... to preserve the full solution set. 
;  A=X , dif(B,X), C=X 
; dif(A,X),  B=X , C=X 
; false.