Prolog difference routine help!

Question

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 occurance that it finds.. how ever I need it to remove all occurances. 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, how ever I know its almost what I want. I didn't use subtract because my final code has to be compatable with WIN-Prolog... I am testing it on SWI prolog.

Answer 1

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

Answer 2

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.

Answer 3

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.