2

My program is intended to get rid of repeating elements in a list. I think its correct. I tried to make it work by putting cuts, but it didn't give correct results.

member(X,[X|_]). % If X is Head, it is a member
member(X,[_|T]) :- member(X,T). % If not, Recursively check the tail.

remove_duplicates([],[]).
remove_duplicates([H|T],R):-member(H,T),remove_duplicates(T,R).
remove_duplicates([H|T],[R|REM]):-remove_duplicates(T,REM).

However I am getting results: I = [_G2608, _G2611, _G2614|_G2615] for input remove_duplicates([a,b,a,b,b,c],I).

false
  • 10,264
  • 13
  • 101
  • 209
ed bale
  • 59
  • 1
  • 9
  • 2
    The last rule should be: `remove_duplicates([H|T],[H|REM]):-\+ member(H, T), remove_duplicates(T,REM).` – Tudor Berariu Jan 16 '15 at 07:48
  • 1
    If you don't insist of keeping the original order of the first occurrence of each element, just `sort/2` your original list –  Jan 16 '15 at 10:45
  • 3
    I suspect you saw a *singleton warning* on your 3rd `remove_duplicates/2` clause due to the "orphan" `R` variable. – lurker Jan 16 '15 at 12:21
  • 2
    People cleverer than me have said that a cut can never make an incorrect program correct. –  Jan 16 '15 at 12:29

2 Answers2

3

Here is a version that is both pure and also more efficient in the sense that it does only need constant auxiliary space. The solutions posted so far require in the worst case space proportional to the size of the list in the first argument. But now to correctness:

?- remove_duplicates([A,B], Fs).

Here we ask:

How must A and B look like to result in a list Fs that has no duplicates?

This question cannot be answered simply by stating the concrete Fs, for this Fs might be [A,B] or [A] should A and B be the same.

?- remove_duplicates([A,B],F).
   A = B, F = [B]
;  F = [A, B], dif(A, B).

And here is a solution to it. This definition requires the monotonic if_/3 and memberd_truth/3 defined in another answer.

remove_duplicates([], []).
remove_duplicates([E|Es], Fs0) :-
   if_( memberd_truth(E, Es) , Fs0 = Fs , Fs0 = [E|Fs] ),
   remove_duplicates(Es, Fs).

Personally, I would prefer a more relational name, like list_unique/2 or list_nub/2 as an allusion towards Haskell.

false
  • 10,264
  • 13
  • 101
  • 209
2

Tudor's solution is good. However, I have come to see the benefits of using conditional statements where appropriate, even though I find the aesthetics a bit lacking, so I would suggest this solution instead:

remove_duplicates([], []).
remove_duplicates([H|T], R) :-
  (   memberchk(H,T)
  ->  remove_duplicates(T, R)
  ;   remove_duplicates(T, R0), 
      R = [H|R0]
  ).

An explicit conditional like this does not create a spurious choice point. It's that choice point which is causing Tudor's solution to require a negated member/2, which you were trying to correct with a cut. So even though it looks less beautiful, it's a somewhat more efficient solution.

Also, using memberchk/2 instead of member/2 is a small optimization for cases where you do not require member/2's ability to generate solutions. Compare:

?- time(remove_duplicates([a,b,a,b,b,c], I)).
% 14 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 1037114 Lips)
I = [a, b, c].

to Tudor's revision of your code:

?- time(remove_duplicates([a,b,a,b,b,c], I)).
% 28 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 2264822 Lips)
I = [a, b, c] ;
% 28 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 1338752 Lips)
I = [a, b, c] ;
% 15 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 1065341 Lips)
false.
Daniel Lyons
  • 22,421
  • 2
  • 50
  • 77
  • After using the Prolog "if-else" in several situations, it's starting to grow on me aesthetically (a little). :) – lurker Jan 16 '15 at 17:49