Returning True if intersection is empty and False otherwise

user_17178229 0
Viewed 157

I have a function that computes the intersection of two list in prolog. code:

list_member(X,[X|_]).
list_member(X,[_|TAIL]) :- list_member(X,TAIL).

list_intersect([X|Y],Z,[X|W]) :-
   list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([X|Y],Z,W) :-
   \+ list_member(X,Z), list_intersect(Y,Z,W).
list_intersect([],_,[]).

I want a function that returns true if the intersection list provided by the above fn is empty else it should return false.

Code tried:

success_fn([X], [Y]) :-
list_intersect(X, Y, Z),
length(Z, L),
L > 0, write('False');
L < 1, write('True').

Query I used:

success([1,2,3,4,5,6], [1, 2, 3]).

The output returns false every time.

prolog
2 Answers

Assuming you have a working intersection predicate, testing for the intersection of two sets being the empty set is trivial:

intersection( [1,3,5,7,9], [2,4,6,8,10], [] ).

Intersection is a set operation (meaning that it operates on unique collections, each without duplicate members. [1,2,3] is a set; [3,2,1,2,2,3] is not a set.)

This is one way to compute the intersection of two sets (sort/2 removes duplicates in addition to ordering the set):

intersection( Xs, Ys, Zs ) :-      % to compute set intersection
  sort(Xs,X1),                     % - ensure the first list is an ordered set
  sort(Ys,Y1),                     % - ensure that the second list is an ordered set
  findall(Z, common(Z,X1,Y1), Zs). % - Find all Z such that Z is common to both Xs and Ys

% Z is common to Xs and Ys if it is a member of both Xs and Ys
common(Z, Xs, Ys) :- member(Z,Xs), member(Z,Ys).
user_4674730

These are not functions, but predicates. Here is a short glossary you can refer to: https://www.swi-prolog.org/pldoc/man?section=glossary. It is not a place you can learn from but at least it presents the terminology.

This is relevant because in Prolog, since you don't have functions, those do not return true nor false, because they don't return anything. What predicates do is explained in most tutorials and I won't go into it here.

Since this is a homework question, I shouldn't give you a ready answer, I don't need the wrath of the Stackoverflow gods. Here is a way to state that the list on the left hand side is empty:

?- My_list = [].

Here is a way to state that the list on the left-hand side is certainly not empty:

?- My_list = [_|_].

Maybe this will help you get started and further improve your question.

A hint (since I am in a good mood right now): try to remove lines from the predicate definition you've got there, starting at the bottom, until you find something that doesn't say "false". At least you will know what fails. At the moment the whole things fails but you don't know where your mistake is. It could be already in the first line of what you have labeled "Code tried" in your question, and everything else you have is both correct and irrelevant to your problem. In programming circles this kind of work is called "debugging" and people usually do it by themselves, since it is the very nature of programming.

user_144119970
Related