CODEWITHSUNDEEP
recursionprolog
ed bale
ed bale

Reputation: 59

Invalid Result in Prolog Program

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

Upvotes: 2

Views: 118

Answers (2)

false
false

Reputation: 10142

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.

Upvotes: 3

Daniel Lyons
Daniel Lyons

Reputation: 22803

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.

Upvotes: 2

Related Questions