Prolog: Determine if the intersection of two lists is empty

Question

I'm trying to figure out how to determine if the intersection of two lists is empty in Prolog. From what I understand, this is they have no elements in common. I'm new to Prolog(as of last night). Any help is greatly appreciated.

Here is my attempt:

% returns true if head is not a member of List?
intersection([],_).
intersection([Head|Tail],List) :- 
   \+ member(Head,List),  
   intersection(Tail,List).

Second Attempt:

?- intersect([A,B,C,D],[E,F,G,H]).

intersect(L1,L2) :-
    intersection(L1,L2,[]).

mbratch's resolution solved the problem.

Solution:

?-intersect([a,b,c,d],[e,f,g,h]).

intersect(L1,L2):-
    intersection(L1,L2,[]).

Thanks for the response. I'm still getting false, not sure what Im missing. I updated the post. Thanks. — pdf2e, Mar 31 '14 at 14:21
You're using variables instead of atoms. Try `intersect([a,b,c,d], [e,f,g,h]).` If you use variables, Prolog will say they can intersect because it will be able to unify `A` with `E` for example, being that they're variables. Variables begin with a capital letter. Atoms ("constants") begin with lower case. — lurker, Mar 31 '14 at 14:28
@ mbratch `intersection/3` is NOT a SWI-Prolog built-in predicate. It's a library predicate defined in the `lists` module. In SWI-Prolog, modules are auto-loaded by default when one of their exported predicates is called. Awareness of the SWI-Prolog auto-loading would go along way in avoiding mistaken library predicates for built-in predicates, an unfortunate common occurrence here on SO. — Paulo Moura, Mar 31 '14 at 15:21
@PauloMoura apologies. I stand corrected. Since I didn't need to include any special libraries, I thought it was built-in. — lurker, Mar 31 '14 at 15:46

Paulo Moura · Answer 1 · 2014-03-31T15:50:13.183

3

A more efficient solution (in general) compared with computing the intersection of the two lists is to fail as soon as a common element is found:

empty_intersection(List1, List2) :-
    \+ (member(Element, List1), member(Element, List2)).

edited Mar 31 '14 at 15:50

answered Mar 31 '14 at 15:25

Paulo Moura

18,373
3
23
33

score 3 · Answer 2 · edited May 23 '17 at 12:10

Stay pure! It's as easy as 1,2,3:

Using meta-predicate maplist/2 and dif/2 (prolog-dif), we define list_nonmember/2:

    list_nonmember(Xs,E) :-
       maplist(dif(E),Xs).

Using maplist/2 and list_nonmember/2, we define none_intersect/2:

    none_intersect(Xs,Ys) :-
       maplist(list_nonmember(Ys),Xs).

Ready to go! Let's run some queries!

    ?- none_intersect([a,b,c,d],[e,f,g,h]).
    true.

    ?- none_intersect([a,b,c,d],[e,f,a,g,h]).
    false.

    ?- none_intersect([a,b,g,c,d],[e,f,g,h]).
    false.

Prolog: Determine if the intersection of two lists is empty

2 Answers2