Prolog: First duplicate value

Question

I need to find the first duplicate value in a list.

prep(3,[1,3,5,3,5]). Should be true.

prep(5,[1,3,5,3,5]). Should be false.

I thought checking for equality with the current value and the previous list members until I find a duplicate, if it finds one it will test for equality with X but I have no idea how to do that in Prolog!

I appreciate any help! Thanks

Dinse

Answer 1

Here is a pure version using dif/2 which implements sound inequality. dif/2 is offered by B-Prolog, YAP-Prolog, SICStus-Prolog and 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).

The advantages are that it can also be used with more general queries:

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

Here, we get three answers: A is the duplicate in the first two answers, but on two different grounds: A might be equal to B or C. In the third answer, B is the duplicate, but it will only be a duplicate if C is different to A.

To understand the definition, read :- as an arrow ← So what is on the right-hand side is what you know and on the left is what you conclude. It is often in the beginning a bit irritating to read predicates in that direction, after all you might be tempted to follow "the thread of execution". But often this thread leads to nowhere – it gets too complex to understand.

The first rule reads:

Provided E is an element of list L we conclude that [E|L] has E as first duplicate.

The second rule reads:

Provided E is the first duplicate of L (don't panic here and say we don't know that ...) and provided that N is not an element of L we conclude that [N|L] has E as first duplicate.

The member/2 predicate is provided in many Prolog systems and non_member(X,L) can be defined as maplist(dif(X),L). Thus one would define firstdup/2 rather as:

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

Alurta

it is perhaps better if the last line of text would read "... and nonmember(X,L) can be defined as maplist(dif(X),L). ...", to give context to X and L there. :) – Neckerchief

Answer 2

In this answer we improve the logically pure code presented in this earlier answer. Step-by-step:

1. We combine two predicates memberd/2 and non_member/2 to one, memberd_t/3, which uses an additional argument for reifying list membership into a truth-value (true or false).

   memberd_t/3 is equivalent to memberd/2 + non_member/2, so we could define it like this:

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

   Or, vice versa, we could define memberd/2 and non_member/2 like so:

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

   In practise, we use a tuned implementation of memberd_t/3—one with better determinism.

   Let's see that memberd_t/3 in fact covers both memberd/2 and 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. Take the following variant of predicate firstdup/2 (defined earlier) as our starting point:

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

3. Let's replace the use of memberd/2 and non_member/2 with memberd_t/3!

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

4. Let's hoist memberd_t/3!

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

5. Above pattern pred_t(OtherArgs,T), (T = true -> Then ; T = false, Else) can be expressed more concisely using if_/3, writing if_(pred_t(OtherArgs),Then,Else).

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

---

Let's run some queries!

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

Browder

Answer 3

Not sure if this is homework/ there are restrictions on which predicates you are allowed to use, but this gets prolog to do the recursion for you.

It says.. find all duplicates ie. where there is an item with list index I1, and another one with I2, such that they both have the same value N, and the indices are not the same ie.don't consider the same list item as a duplicate.

These duplicates are put (in the order they are found, from the beginning crucially) in list AllDups, and the predicate is true if the first duplicate found unifies with M, the value you are checking.

First Attempt: This works but is very inefficient, building a list of ALL duplicates

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.

Even if you are not allowed to use findall, it might help you work out how to do it 'manually'.

Second Attempt: This doesn't work / backtracks too far yielding a false positive

You can even do it without the findall - use nth0 to find the first duplicate item, then if that unifies with the value you are checking, it returns true, otherwise false.

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

Third Attempt : This works, and returns as soon as the first duplicate has been found

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

Washerwoman

I'm still a Prolog begginer and this is a bit tough for me to understand. We aren't taught Prolog in classes and i barely have time to learn it decently on my own, this exercise was only given has self-study though so i'll try to understand it better later. Thank you for your time! :) – Dinse

You're welcome.. it's a strange language, have no doubt. It does so much for you, rather than you having to tell it what to do all the time, and so you need to understand what it can do behind the covers to come up with the neatest solution. – Washerwoman

with your last addition, prep(5,[1,3,5,3,5]). returns true as well. ?- prep(N,[1,3,5,3,5]). N = 3 ; N = 5 ; N = 3 ; N = 5 ; No. – Neckerchief

@false: I1 and I2 are the indexes of the lists.. ie find two list items in list 'List' who have identical value 'N', but whose indices are different. – Washerwoman

@will ness - yep - I thought I tested that. I have put in a fixed version as Edit 2 above. My first solution is VERY inefficient.. building a list of all duplicates first. Edit 2 contains a cut to ensure that after two matching values have been found with different indices, it will not backtrack with another nth0 value should the input value not match the value found. – Washerwoman

hi, now it seems as though it should work; it's probably better if you'd clearly state in your answer which code is working properly and which doesn't. – Neckerchief

Thanks Will - inserted as requested. – Washerwoman

Answer 4

rep(N,List) :- append(L1,[N|_],List),append(_,[N|_],L1),\+(rep(_,L1)).

Stretcherbearer