CODEWITHSUNDEEP
listprolog
rwehresmann
rwehresmann

Reputation: 1178

Prolog: Build a list with repeated elements of other list

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?

Upvotes: 2

Views: 2374

Answers (4)

repeat
repeat

Reputation: 18726

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

We define list_uniqdups/2 based upon 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.

Upvotes: 4

Sheshnath
Sheshnath

Reputation: 301

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.

Upvotes: 0

repeat
repeat

Reputation: 18726

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

  1. 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).

  2. 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).

  3. Let re-run the query the OP gave!

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

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

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

Upvotes: 3

CapelliC
CapelliC

Reputation: 60034

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.

Upvotes: 2

Related Questions