Пролог: первое повторяющееся значение

Вот чистая версия с использованием 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, и non_member(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).

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

1. Мы объединяем два предиката memberd/2 и _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 - более детерминированную.

   Давайте посмотрим, что 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 (определенный ранее) в качестве отправной точки:

   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.

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

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

Там написано .. найти все дубликаты т.е. где есть элемент с индексом списка 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.