Find the unique elements only that are not in both two lists

Question

Compute the symmetric difference of two lists and return a third list containing no duplicates.

Sample query showing expected results:

?- join([a,b,p,l,a,f],[q,a,z,x,l],Rs).
Rs = [b,p,f,q,z,x].

I currently have this code:

join([],List,List).
join([H|T],List,[H|Result]) :-
    not(member(H,List)),
    join(T,List,Result).
join([H|T],Y,Z) :-
    join(T,Y,Z).

It can find all the elements that do not repeat, but it places them all as the head on the second list.

How can I make it so the second list is also checked for elements that are repeated and only output those which are not?

Are you certain your example is correct? I'm wondering why `l` appears in the result if it appeared in both input lists. — , May 19 '11 at 02:10
Ok yeah, the answer should not include l. That was a mistake. — HelloAndGoodbye, May 20 '11 at 15:03

score 2 · Answer 1 · edited May 23 '17 at 12:05

2

The "non-intersection" you describe seems to be the symmetric difference of two sets, which is the union of both their (asymmetric) set differences. Set difference can be computed with the SWI-Prolog subtract/3 predicate or the solution to this problem.

Getting the union can be done with append/3 followed by sort/2, which takes care of the duplicates.

edited May 23 '17 at 12:05

Community

1
1

answered May 17 '11 at 19:04

Fred Foo

355,277
75
744
836

score 1 · Answer 2 · edited May 23 '17 at 10:26

The following implementation preserves logical-purity. It is based on:

the meta-predicates tfilter/3 and tpartition/4,
the monotone if-then-else control construct if_/3,
the reified unary logical connective not_t/3,
the reified term equality predicate (=)/3,
and the pure "list to set" predicate list_setB/2 defined in a previous answer.

Let's get straight to the code!

list_list_symdiffset([],Ys,Zs) :-
   list_setB(Ys,Zs).
list_list_symdiffset([X|Xs0],Ys0,Zs0) :-
   tpartition(=(X),Ys0,Es,Ys1),
   if_(Es=[], Zs0=[X|Zs1], Zs0=Zs1),
   tfilter(not_t(=(X)),Xs0,Xs1),
   list_list_symdiffset(Xs1,Ys1,Zs1).

Let's run the sample query given by the OP:

?- list_list_symdiffset([a,b,p,l,a,f],[q,a,z,x,l],Rs).
Rs = [b,p,f,q,z,x].                   % succeeds deterministically

At last, let's try something more general!

?- list_list_symdiffset([A,B],[X,Y],Ys).
Ys = [],        A=B, B=X, X=Y ;
Ys = [B],       A=X, X=Y, dif(Y,B) ;
Ys = [Y],       A=B, B=X, dif(X,Y) ;
Ys = [],        A=X, B=Y, dif(X,Y), dif(X,Y) ;
Ys = [B,Y],     A=X, dif(X,B), dif(X,Y), dif(B,Y) ;
Ys = [X],       A=B, B=Y, dif(Y,X) ;
Ys = [],        A=Y, B=X, dif(Y,X), dif(Y,X) ;
Ys = [B,X],     A=Y, dif(Y,B), dif(Y,X), dif(B,X) ;
Ys = [B,Y],     A=B, X = Y, dif(B,Y), dif(B,Y) ;
Ys = [B,X,Y],   A=B, dif(B,Y), dif(B,X), dif(X,Y) ;
Ys = [A],       B=X, X=Y, dif(A,Y), dif(A,Y),dif(A,Y) ;
Ys = [A,Y],     B=X, dif(A,X), dif(A,Y), dif(A,X), dif(X,Y) ;
Ys = [A,X],     B=Y, dif(A,Y), dif(A,Y), dif(A,X), dif(Y,X) ;
Ys = [A,B,Y],   X=Y, dif(A,B), dif(A,Y), dif(A,Y), dif(B,Y), dif(B,Y) ;
Ys = [A,B,X,Y], dif(A,B), dif(A,Y), dif(A,X), dif(B,Y), dif(B,X), dif(X,Y).

score 0 · Answer 3 · answered May 17 '11 at 22:56

0


join(L1,L2,L) :-
        append(L1,L2,L3),
        findall(A,unique(L3,A),L).

unique(L3,A) :-
        append(L0,[A|R],L3),
        \+(append(_,[A|_],L0)).

answered May 17 '11 at 22:56

尾崎隆大

148
1
1

1

This definition of `join/3` returns the set of unique elements of a concatenation of two lists, which is not what the OP asked for. – May 19 '11 at 02:07

Find the unique elements only that are not in both two lists

3 Answers3