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

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!

CodePudding user response：

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

CodePudding user response：

You are right, the problem is simple but might not be because you give a simple example, what happens if exists two 5? if I have more 1 or 2? The list A is remove if there is more 3's? But first lets look for the simple example. First this ==true don't exist in prolog. Second If I was you I should divide this function in 2. The first is removing elements form List A take are equal for the elements in List B (member function might help you but you can do you're remove function by yourself). The second part is check if list A is equal to C (with member) and if yes, return true, else is false. I suggest you to check more examples in google and study more the functioning of lists in prolog and methods capable of helping in more complicated functions (member, intersection, union,...) and with that you will be able to do your function. Also recursion on functions is very useful in prolog so it might also help you in the remove part I talk :)

Edit

This might help you (if you are not allow to use sort), this just connects two Lists into One

connect([],B,B).
connect([X|B],C,[X|L]):-connect(B,C,L).

After this maybe you need to do the member function (if you are not allow you can find something similiar because generic functions are normal functions that are useful for larger functions and help you write less code)