CODEWITHSUNDEEP
prologlogic
SteveW
SteveW

Reputation: 41

Prolog difference routine

I need some help with a routine that I am trying to create. I need to make a routine that will look something like this:

difference([(a,b),(a,c),(b,c),(d,e)],[(a,_)],X).

X = [(b,c),(d,e)].

I really need help on this one..

I have written a method so far that can remove the first occurrence that it finds.. however I need it to remove all occurrences. Here is what I have so far... 

memberOf(A, [A|_]).
memberOf(A, [_|B]) :-
    memberOf(A, B).

mapdiff([], _, []) :- !.
mapdiff([A|C], B, D) :-
        memberOf(A, B), !,
        mapdiff(C, B, D).
mapdiff([A|B], C, [A|D]) :-
        mapdiff(B, C, D).

I have taken this code from listing(subtract).

I don't fully understand what it does, however I know it's almost what I want. I didn't use subtract because my final code has to be compatible with WIN-Prolog... I am testing it on SWI Prolog.

Upvotes: 4

Views: 619

Answers (3)

user206428
user206428

Reputation:

Tricky one! humble coffee has the right idea. Here's a fancy solution using double negation:

difference([], _, []).
difference([E|Es], DL, Res) :-
    \+ \+ member(E, DL), !,
    difference(Es, DL, Res).
difference([E|Es], DL, [E|Res]) :-
    difference(Es, DL, Res).

Works on SWI-PROLOG. Explanation:

Clause 1: Base case. Nothing to diff against!

Clause 2: If E is in the difference list DL, the member/2 subgoal evaluates to true, but we don't want to accept the bindings that member/2 makes between variables present in terms in either list, as we'd like, for example, the variable in the term (a,_) to be reusable across other terms, and not bound to the first solution. So, the 1st \+ removes the variable bindings created by a successful evaluation of member/2, and the second \+ reverses the evaluation state to true, as required. The cut occurs after the check, excluding the 3rd clause, and throwing away the unifiable element.

Clause 3: Keep any element not unifiable across both lists.

Upvotes: 4

nedned
nedned

Reputation: 3707

Your code can be easily modified to work by making it so that the memberOF predicate just checks to see that there is an element in the list that can be unified without actually unifying it. In SWI Prolog this can be done this way:

memberOf(A, [B|_]) :- unifiable(A,B,_).

But I'm not familiar with WIN-PRolog so don't know whether it has a predicate or operator which only tests whether arguments can be unified.

Upvotes: 2

Alexey Romanov
Alexey Romanov

Reputation: 170745

I am not sure, but something like this could work. You can use findall to find all elements which can't be unified with the pattern:

?- findall(X, (member(X, [(a,b),(b,c),(a,c)]), X \= (a,_)), Res).

gets the reply

Res = [ (b, c) ]

So

removeAll(Pattern, List, Result) :-
  findall(ZZ109, (member(ZZ109, List), ZZ109 \= Pattern), Result).

should work, assuming ZZ109 isn't a variable in Pattern (I don't know a way to get a fresh variable for this, unfortunately. There may be a non-portable one in WIN-Prolog). And then difference can be defined recursively:

difference(List, [], List).
difference(List, [Pattern|Patterns], Result) :- 
  removeAll(Pattern, List, Result1),
  difference(Result1, Patterns, Result).

Upvotes: 3

Related Questions