Set Intersection predicate Prolog using not

Question

I am trying to build a simple predicate which get as inputs two lists and the results is a third one consisting of the intersection of the first two. I have decided to do using logical statement. I am pretty sure my logic is correct but my predicate is not working. Any ideas?:

element(X,[H|T]) :- 
      X=H
   ;
      element(X,T).

intersection(L1,L2,R) :-
    not((
        element(A,L1),
        not(element(A,L2))
    )),
    not((
        element(A,L1),
        not(element(A,R))
    )).

Please do not post alternative methods I am wondering why this one returns FALSE every time.

Answer 1

Your definition is correct too general. It admits e.g. that [] is the intersection of any two lists which is too general. I.e. it incorrectly succeeds for intersection([],[a],[a]). It lacks a third "for all" idiom stating that all elements that are in both lists will be in the resulting list.

But otherwise your definition is fine. For the ground case. What is a bit unusual is that the intersection is the first and not the last argument. Quite irritating to me are the variable names. I believe that R means "result", thus the intersection. And L1 and L2 are the two sets to build the intersection.

It is a bit too general, though - like many Prolog predicates - think of append([], non_list, non_list). Apart from lists, your definition admits also terms that are neither lists nor partial lists:

?- intersection(non_list1,[1,2|non_list2],[3,4|non_list3]).

To make it really useful safe, use it like so:

?- when(ground(intersection(I, A, B)), intersection(I, A, B)).

or so:

?- (  ground(intersection(I, A, B))
   -> intersection(I, A, B)
   ;  throw(error(instantiation_error, intersection(I, A, B)))
   ).

Or, using iwhen/2:

?- iwhen(ground(intersection(I, A, B)), intersection(I, A, B) ).

---

As a minor remark, rather write (\+)/1 in place of not/1.

Answer 2

The problem is that not/1 merely negates the outcome of your element/2. It doesn't cause element/2 to backtrack to find other instantiations for which the enclosing not/1 will be true.

Consider the following program.

a(1).
a(2).

b(1).
b(2).
b(3).

And the following queries:

1. b(X), not(a(X)).
2. not(a(X)), b(X).

The first one yields X = 3 while the second one yields false. That is because the first query first instantiates X with 1, then with 2, then with 3, until finally not(a(X)) succeeds.
The second query first instantiates X with 1, a(1) succeeds, so not(a(1)) fails. There is no backtracking done!