Prolog: splitting a list into two lists (unique elements / duplicates)

Question

I am trying to break this list down into two different lists: Unique and Duplicate. For example, if we have a list [1, 1, 2, 3, 3, 4, 5] , I want the unique list to be [2, 4, 5] , and Duplicate to [1, 3] . I do not want all 1 in the list to be in the Duplicate list. I just need one. The code I have right now is:

 compareL([_|[]], Unique, Dup). compareL([X3,Y3 | Tail], [X3 | Unique], Dup) :- X3 =\= Y3, compareL([Y3 | Tail], Unique, Dup). compareL([X3,Y3 | Tail], Unique, [X3 | Dup]) :- X3 = Y3, skipDups(X3, Tail, Unique, Dup). skipDups(_, [], Unique, Dup). skipDups(X3,[Y3 | Tail], Unique, Dup) :- X3 =\= Y3, compareL([Y3 | Tail], Unique, Dup). skipDups(X3,[Y3 | Tail], Unique, Dup) :- X3 = Y3, skipDups(X3, Tail, Unique, Dup). 

Using the list of examples above, if I ran compareL([1, 1, 2, 3, 3, 4, 5], Unique, Dup). , I get:

 Unique = [2, 4|_G1954], Dup = [1, 3|_G1948]. 

I can’t understand why at the end of both lists I get " _G1954 " and " _G1948 ". Any help would be greatly appreciated. Thanks.

Answer 1

here is the solution, the key is take / 4, which consumes all matching leading elements, which makes it easy to test the list ( [_|_] matches any list with at least 1 element)

 compareL([], [], []). compareL([X|Xs], U, D) :- ( take(X, Xs, [_|_], Ys) -> compareL(Ys, U, B), D = [X|B] ; compareL(Xs, A, D), U = [X|A] ). take(X, [X|Xs], [X|R], Ys) :- !, take(X, Xs, R, Ys). take(_, Ys, [], Ys). 

Answer 2

We can preserve logical-purity by creating on if_/3 , (=)/3 and tpartition/4 !

 list_uniqs_dups([],[],[]). list_uniqs_dups([X|Xs0],Us0,Ds0) :- tpartition(=(X),Xs0,Es,Xs), if_(Es=[], Us0+Ds0=[X|Us]+Ds, Ds0+Us0=[X|Ds]+Us), list_uniqs_dups(Xs,Us,Ds). 

Here the OP query gave:

 ?- list_uniqs_dups([1,1,2,3,3,4,5],Us,Ds). Ds = [1,3], Us = [2,4,5]. % succeeds deterministically 

OK! What about the following fairly general queries?

  ? - list_uniqs_dups ([], Us, Ds).
 Ds = [], Us = [].

 ? - list_uniqs_dups ([A], Us, Ds).
 Ds = [], Us = [A].

 ? - list_uniqs_dups ([A, B], Us, Ds).
   Ds = [B], Us = [], A = B
 ;  Ds = [], Us = [A, B], dif (A, B).

 ? - list_uniqs_dups ([A, B, C], Us, Ds).
   Ds = [C], Us = [], A = B, B = C
 ;  Ds = [B], Us = [C], A = B, dif (B, C)
 ;  Ds = [C], Us = [B], A = C, dif (B, C)
 ;  Ds = [C], Us = [A], dif (A, C), B = C
 ;  Ds = [], Us = [A, B, C], dif (A, B), dif (A, C), dif (B, C).

Answer 3

Answer with (=)/3

 list_uniqs_alldups(Es,Us,Ds) : tpartition(list_uniqmember_t(Es),Es,Us,Ds). list_uniqmember_t(Es,X,T) :- tfilter(=(X),Es,Xs), =(Xs,[X],T). 

Request examples:

 ?- list_uniqs_alldups([1,1,2,1,1,3,4,3],Us,Ds). Us = [2, 4], Ds = [1, 1, 1, 1, 3, 3]. ?- list_uniqs_alldups([1,1,2,3,3,1,1,3,4,3],Us,Ds). Us = [2, 4], Ds = [1, 1, 3, 3, 1, 1, 3, 3]. ?- list_uniqs_alldups([8,1,1,2,3,3,1,1,3,4,3],Us,Ds). Us = [8, 2, 4], Ds = [1, 1, 3, 3, 1, 1, 3, 3]. ?- list_uniqs_alldups(X,Us,Ds). X = Us, Us = Ds, Ds = [] ; X = Us, Us = [_A], Ds = [] ; X = Ds, Us = [], Ds = [_A,_A] ; X = Ds, Us = [], Ds = [_A,_A,_A] ; ... 

To encode the length of the path, I used splitlistIfAdj/3 .

 list_rle(List,Rle) :- splitlistIfAdj(dif,List,Rle0), maplist(rle_length,Rle0,Rle). rle_length([H|T],RleLen) :- length([H|T],L), RleLen = L*H. 

Query:

 ?- list_rle([a,a,b,a,a,c,d,c],X). X = [2*a, 1*b, 2*a, 1*c, 1*d, 1*c]. 

I'm not sure how to change this so that it works in both directions.

Then you can also:

 new_list_uniqs_alldups(List,Us,Ds):- list_rle(List,Rle), tpartition(singlelist_t,Rle,Us,Ds). singlelist_t(L,T) :- L=N*_, if_(N=1,T=true,T=false). 

Example Q:

  ?- new_list_uniqs_alldups([1,1,2,1,1,3,4,1,1,7,8],U,D). U = [1*2, 1*3, 1*4, 1*7, 1*8], D = [2*1, 2*1, 2*1]. ?- new_list_uniqs_alldups([7,7,7,2,1,1,3,4,1,1,7,8],U,D). U = [1*2, 1*3, 1*4, 1*7, 1*8], D = [3*7, 2*1, 2*1]. 

Answer 4

You can write this:

 split_seq([], [], []). split_seq([H | T], L1_out, L2_out) :- split_seq(T, L1, L2), ( select(H, L1, L1_out) -> ( member(H, L2) -> L2_out = L2 ; L2_out = [H | L2]) ; L1_out = [H | L1], L2_out = L2).