Check if List C is the difference of List A and List B

Question

I am trying to write a Prolog program which returns true if list C is list A without List B ( so using set operators: C = A \ B )

difference(A,B,C) :-

?- difference([1,2,3,5],[1,2,3], [5]).
true
?- difference([1,2,3,5,5],[1,2,3], [5]).
false
?- difference([4,7,6],[4,6], [7]).
true

Although this problem looks simple (might not be) I just can not figure it out.

Cheers!

Answer 1

Since you are not allowed to use built-in predicates, you should start by creating a predicate that succeeds only if an element is member of a list.

member_of(X, [X|_]).
member_of(X, [_|L]) :- member_of(X, L).

Then you can use this predicate to create the predicate difference/3:

difference([], _, []).
difference([X|A], B, R) :-
    (   member_of(X, B)
    ->  R = C
    ;   R = [X|C] ),
    difference(A, B, C).

Examples:

?- difference([1,2,3,5], [1,2,3], [5]).
true.

?- difference([1,2,3,5,5], [1,2,3], [5]).
false.

?- difference([4,7,6], [4,6], [7]).
true.

?- difference([1,2,3,5], [1,2,3], D).
D = [5].

?- difference([1,2,3,5,5], [1,2,3], D).
D = [5, 5].

?- difference([4,7,6], [4,6], D).
D = [7].

Or the predicate difference_without_duplicates/3:

difference_without_duplicates([], _, []).
difference_without_duplicates([X|A], B, R) :-
    difference_without_duplicates(A, B, C),
    (   (   member_of(X, B)
        ;   member_of(X, C) )
    ->  R = C
    ;   R = [X|C] ).

Examples:

?- difference_without_duplicates([1,2,2,3,5,5], [1,2,3], D).
D = [5].

?- difference_without_duplicates([4,7,1,7,6],[4,6,6], D).
D = [1, 7].