Writing a prolog predicate for diff/3

[avillachandok]

Hi,
I need to write a prolog predicate for diff/3 without using the built-in predicate subtract/3. The diff/3 predicate for example gives as follows:

?-diff([1,3,3,4],[4,5,8],X)
X=[1,3]

The diff(List1,List2,X) predicate takes List 1 and List 2 and unifies a new list X with all elements in List1 that do not appear in List 2. List1 is assumed to contain no duplicate elements.

[Nick Evan]

Well, good luck with that!

[avillachandok]

Hi,
I am familiar with the rules of this site and wasn't looking for a solution but rather something that can help me start of my solution with. However, here is a solution that I've come up with but since I've never written prolog in my life, I'm not sure how good this is.
Basically I've used the remove_duplicate/2 predicate that was defined in the text but if it doesn't exist here is the prolog program for that.

remove_duplicates([],[]).                                              //base case
remove_duplicates([Head|Tail], Result):-                       //recursive case
     member(Head|Tail),!,                                       
     remove_duplicates(Tail,Result).

remove_duplicates([Head|Tail],[Head|Result]):-
     remove_duplicates(Tail, Result).

This prolog program has a cut so that it doesn't backtrack into giving wrong results. The basic idea is that if the list(1st argument) in remove_duplicates is empty then the base case succeeds. If however, there are elements in the list then it performs a recursive case where it checks if there are any similar elements in the Tail that match the head of the list and is removed otherwise the second rule is performed and the head is added to the resultant list.

Now here is the prolog program I wrote for the diff/3 predicate without using the built-in subtract predicate. Look at the above post for what it is supposed to do.

diff([],[],[]).                                         //base case
diff([],List2,[]).                                     //base case

diff([Head|List1], List2, Y):-                 //recursive case
     remove_duplicates([Head|List1], [Head1|NewList1]),
     member(Head1, List2),
     diff(NewList1, List2, Y).

diff([Head|List1], List2, Y):-                //peforms as ^(same head rule)
     remove_duplicates([Head|List1], [Head1|NewList1]),
     diff(NewList1, List2, [Head1|Y]).

The base case succeeds if both lists are empty or if the first list is empty since the diff is then an empty list.

The first rule states that if we have elements in the first list then first any duplicate elements are removed from List1 itself using the remove_duplicates and renamed NewList1. Then the Head of the NewList1 is checked with List2 and if there is any match the Head is dicarded or the head is kept from the second rule.

Questions.
I don't know if the remove_duplicates predicate used in both the rules should be used in both places. Also, I don't know if there should be a cut in the first rule after the first sub-goal just as in the case of the remove_duplicates. I'm not familiar with the cut and tried making sense of it but can't.
I have looked at examples but I can't correlate well with this one.
Any help would be appreciated.
Cheers.