CODEWITHSUNDEEP
prolog
TheLeftRight
TheLeftRight

Reputation: 33

Removing unique elements from list in prolog

I am attempting to remove unique elements from a list in Prolog.

Output should look something like:

?- rem_Uniq([3,3,1,7,a,c,c],D).
D = [3, c].

Here is my current code.

rem_Uniq(L1,L2).
rem_Uniq([L1|RL1], [L1|D]) :-
    member(L1,RL1),
    rem_Uniq(RL1,D).
rem_Uniq([L1|RL1], D) :-
    remove(L1[L1|RL1], O),
    rem_Uniq(O, D).

Currently it just returns true no matter what I do (whether I enter I list containing unique variables or not).

Anyone have any ideas or suggestions on what I am doing wrong?

Upvotes: 1

Views: 625

Answers (2)

joel76
joel76

Reputation: 5605

D is the set of elements of the list which appears only one time.

In Prolog "an element which appears only one time in a list" can be translate by

select(X, L, L_X),
\+member(X, L_X)

In Prolog exist predicates that collect element with a certain property setof/3 and bagof/3.

bagof collect all the elements, setof keeps only one element. So you can write

rem_uniq(In, Out) :-
    setof(X, In_X^(select(X, In, In_X),\+member(X, In_X)), Out).

[EDIT]

Now we want only elements that are duplicated in a list. If I remove one of these elements of the list, it will remain other elements of the same value in the list so it can be translated in Prolog by

select(X, In, In_X),
member(X, In_X)

(we say that select(X, In, In_X),member(X, In_X) succeed). Now the code can be written

rem_uniq(In, Out) :-
    setof(X, In_X^(select(X, In, In_X),member(X, In_X)), Out).

For example

?- rem_uniq([3,3,1,7,a,c,c],D).
D = [3,c].

Note that setof will fail if there no elements available

 ?- rem_uniq([3,1,7,a,c],D).
false.

Upvotes: 1

Daniel Lyons
Daniel Lyons

Reputation: 22803

Well, your first problem is your first clause:

rem_Uniq(L1,L2).

This literally says "Any two things are rem_Uniq to each other." This is what's giving rise to always getting true with no unifications. You probably meant this:

rem_Uniq([], []).

Your second problem is that this is not valid syntax:

 remove(L1[L1|RL1], O),

Specifically, L1[L1|RL1], I am unclear what you meant there. I think you meant this delete(L1, [L1|RL1], O).

Now, algorithmically, I think you're a little confused. In clause #2, you prepend L1 to D in the result, which is to say, after knowing that L1 is present in RL1 and using the recursive call to remove it from D. But then in clause #3, you just remove it from [L1|RL1] to make O, which you then remove uniques from.

Each clause of a recursive predicate should represent a case you have to worry about. I don't really see what these clauses mean. The first one should be, in case where the list is empty. The second one should be the case where the list is not empty. What you seem to be trying to do here is something like, in the case where the list is not empty and contains the head element, and the case where it is not empty and does not contain the head element, but the distinction between having or not having that element is (or ought to be) meaningless to your library routine. In other words, delete/3 in one non-empty recursive case should be totally sufficient for this problem:

rem_uniq([], []).
rem_uniq([X|Xs], [X|UniqueXs]) :- 
  delete(X, Xs, XsWithoutX),
  rem_uniq(XsWithoutX, UniqueXs).

So, I think you have a little confusion about when and why you should have multiple clauses, and I think your choice of variable names may have made life harder on yourself. But that's just my guess.

Hope this helps!

Upvotes: 0

Related Questions