Member Avatar for 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.

  • 2 Contributors
  • 2 Replies
  • 263 Views
  • 23 Hours Discussion Span
  • Latest Post Latest Post by avillachandok

Dani AI

Generated

— you can make this much simpler. If List1 is truly guaranteed to have no duplicates, do one pass over List1: for each element, test membership in List2; if it’s present skip it, otherwise add it to the result. Calling a duplicate-removal predicate every recursion is expensive and unnecessary.

A clear, purely declarative version (no explicit cuts) looks like this:

diff([], _, []).
diff([H|T], Exclude, R) :-
    (   member(H, Exclude)
    ->  diff(T, Exclude, R)
    ;   R = [H|Rtail],
        diff(T, Exclude, Rtail)
    ).

Step-by-step: the base case returns an empty result for an empty List1. For each head H, the if-then-else checks membership in List2 (here named Exclude). If member/2 succeeds, H is skipped; otherwise H is prepended to the result and recursion continues.

If you prefer an explicit two-clause style, put the cut after the membership test so Prolog won't try the “include” clause when the element is found:

diff([], _, []).
diff([H|T], Exclude, R) :-
    member(H, Exclude), !,
    diff(T, Exclude, R).
diff([H|T], Exclude, [H|R]) :-
    diff(T, Exclude, R).

Notes and troubleshooting: the example in your post contains duplicate 3s in List1 — if duplicates are actually possible, either remove duplicates once before calling diff/3 or ensure you don’t add the same element twice (for example, preprocess List1 into a unique list). Avoid calling remove_duplicates inside each recursive step. Complexity is O(n*m) for simple membership tests; if List2 is large and performance matters, convert it once to a faster lookup (sorted set or a hash-based structure provided by your Prolog system) or use a merge-style algorithm after sorting.

Recommended Answers

All 2 Replies

Member Avatar for Nick Evan

Well, good luck with that!

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.