Prolog: Build a list with repeated elements of other list

Question

I need construct a predicate who receive a list, check who are the repeated elements and return other list with them. Example:

?- rep_elements([a,b,c,a,b,d], Xs).
Xs = [a,b].

I start building a basic structure, but I don't now how to finish this predicate, or if this it the better way:

exists(Elem, [Elem|_]).
exists(Elem, [H|T]) :-
    exists(Elem, T).

rep_elements([], []).
rep_elements([H|T], [Y|Z]) :-
    exists(H, T),
    rep_elements(T, Z).

Any suggestions?

Possible duplicate of [Prolog: splitting a list into two lists (unique items / duplicate items)](http://stackoverflow.com/questions/15850183/prolog-splitting-a-list-into-two-lists-unique-items-duplicate-items) — repeat, Oct 16 '15 at 22:49

score 4 · Accepted Answer · edited May 23 '17 at 12:08

4

First, I suggest we use a more descriptive predicate name, list_uniqdups.

We define list_uniqdups/2 based upon meta-predicate tpartition/4, if_/3 and (=)/3:

list_uniqdups([],[]).
list_uniqdups([X|Xs0],Ys0) :-
   tpartition(=(X),Xs0,Es,Xs),
   if_(Es=[], Ys0=Ys, Ys0=[X|Ys]),
   list_uniqdups(Xs,Ys).

Sample queries:

?- list_uniqdups([a,b,c,a,b,d],Xs).  % query as given by the OP
Xs = [a,b].                          % expected result

?- list_uniqdups([a,c,b,a,b,d],Xs).  % similar query
Xs = [a,b].                          % same result

?- list_uniqdups([b,c,a,a,b,d],Xs).  % now, `b` comes before `a`
Xs = [b,a].                          % retain the original order

?- list_uniqdups([a,a,a,a,b],Xs).
Xs = [a].                            % remove all duplicates

Note that all above queries succeed deterministically.

edited May 23 '17 at 12:08

Community

1
1

answered Oct 17 '15 at 14:40

repeat

18,496
4
54
166

@false. Highlighting ok? (should be somewhat more decent than before) – repeat Oct 18 '15 at 09:28
That is a very interesting solution. I'll study more closely meta-predicates to understand what make possible this solution. Thanks! – rwehresmann Oct 18 '15 at 19:11
@RodrigoE. By all means! Meta-predicates enable an idiomatic high-level programming style. For a start with meta-predicates, I suggest you **first** look at `maplist/2` ( more info: http://stackoverflow.com/a/6683502/4609915 and https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue#maplist ). Learn how to use it and how it works. Then return and study `tpartition/4`. – repeat Oct 18 '15 at 21:17

score 3 · Answer 2 · edited May 23 '17 at 11:58

Let's re-work your code step-by-step!

The predicate exists/2 is covered by the widely available member/2. Let's use that one!

rep_elements([], []).
rep_elements([H|T], [Y|Z]) :-
   member(H, T),
   rep_elements(T, Z).

As @CapelliC said, rep_elements/2 is missing a clause; we add one using non_member/2!
```
rep_elements([H|T], Z) :-
   non_member(T,H),
   rep_elements(T,Z).
```

Let re-run the query the OP gave!

?- rep_elements([a,b,c,a,b,d],Xs).
  Xs = [a,b]
; false.

OK! Are we done? Not quite! Consider the following query and the answers we get:

?- rep_elements([a,a,a,a,b],Xs).
  Xs = [a,a,a]                 % (1) duplicate items are retained
; Xs = [a,a,a]                 % (2) redundant answer
; Xs = [a,a,a]                 % (2)
; Xs = [a,a,a]                 % (2)
; Xs = [a,a,a]                 % (2)
; Xs = [a,a,a]                 % (2)
; false.                       % (3) leaves behind useless choicepoint

What's next? Take a step back and work on the specification!

Only to explain, I usualy use my own predicates (`exists/2` instead `member/2` and so on) because so I can check step by step the predicate running when I'm debugging, what isn't possible with buil-in predicates. — rwehresmann, Oct 18 '15 at 19:08

score 2 · Answer 3 · answered Oct 17 '15 at 11:11

rep_elements/2 is missing the handling of non duplicated elements.

If exists/2 would also 'return' the list T after having removed the duplicates found, then we could use the cleaned list for the recursion, and the task would be complete. Of course, exists/2 should become exists/3, and maybe renamed to a better, more descriptive name.

score 0 · Answer 4 · answered Oct 18 '15 at 01:47

You can recursively check if the head of the list is in the tail of the list then add it to Result. Your solution can be modified as:

exists(Elem, [Elem|_]).
exists(Elem, [H|T]) :-
     exists(Elem, T).
/* IF you get empty list*/
rep_elements([], []).

/* If repetition found in list then joining it to head of list*/
rep_elements([H|T], Result) :-
     exists(H, T),
     rep_elements(T, [H|Result]).

/* If head of list is not found in the Tail of list*/
rep_elements(H|T, Result):-
     not(exists(H,T)),
     rep_elements(T,Result).

This should work.

Prolog: Build a list with repeated elements of other list

4 Answers4