Using Prolog to find Intersecting Lists

Question

I'm having trouble trying to debug this code of mine to find the intersection between two lists...

For Example: List1 = [3, 4, 5, 6] and List2 = [5, 1, 0, 2, 4].

So, the intersecting lines would be stored into List3 would be [4, 5].

So here's the code for Prolog.

Any help would be appreciated!!!

setIntersection([], [], []).
setIntersection([], _, []).

setIntersection([X|Xs], Y, [Z|W]) :-
    keepDuplicates(X, Y, [Z|Zs]),
    setIntersection(Xs, Y, W).

keepDuplicates(_, [], []).
keepDuplicates([], _, []).
keepDuplicates([], [], []).

% Check if the head of the first list is not a match to the
% first head of the second list
keepDuplicates(G, [H|Hs], Line) :-
    G \= H,
    keepDuplicates(G, Hs, Line).

% Check if the head of the first list
% Does match to the head of the second list
keepDuplicates(G, [G|Gs], [G|NewLine]) :-
    keepDuplicates(G, Gs, NewLine).

It is probably easier to sort both lists first; look here (http://www.swi-prolog.org/pldoc/doc/home/vnc/prolog/lib/swipl/library/ordsets.pl?show=src#ord_intersect/2) for a very idiomatic solution to finding the intersection of ordered lists. — , Mar 20 '14 at 06:09
I agree with @Boris. If you are treating lists as sets, and since sets are "unordered", then you should be able to use a list ordering that is an advantage in handling. — lurker, Mar 20 '14 at 13:23

score 2 · Answer 1 · edited May 23 '17 at 12:05

You can find a couple of logically pure, monotone implementations of list intersection and union in my answer to the related question "Intersection and union of 2 lists".

Let's see a sample query:

?- list_list_intersection([3,4,5,6],[5,1,0,2,4],Intersection).
Intersection = [4,5].             % succeeds deterministically

As the proposed implementation is monotone, you can also use it in more general ways and still get logically sound answers:

?- L2 = [_,_,_], list_list_intersection([3,4,5,6],L2,[4,5]).
L2 = [ 4, 5,_A], dif(_A,6), dif(_A,3)                      ;
L2 = [ 4,_A, 5], dif(_A,6), dif(_A,5), dif(_A,3)           ;
L2 = [ 5, 4,_A], dif(_A,6), dif(_A,3)                      ;
L2 = [_A, 4, 5], dif(_A,6), dif(_A,5), dif(_A,4),dif(_A,3) ;
L2 = [ 5,_A, 4], dif(_A,6), dif(_A,4), dif(_A,3)           ;
L2 = [_A, 5, 4], dif(_A,6), dif(_A,5), dif(_A,4),dif(_A,3) ;
false.

CapelliC · Answer 2 · 2014-03-20T07:04:43.417

Usually sets in Prolog are represented with sorted lists, then avoiding the ambiguity of the representation that arises in presence of duplicate elements. Let's ignore this problem...

This fact setIntersection([], [], []). is subsumed by setIntersection([], _, [])., then can (should!) be deleted. The same for keepDuplicates([], [], []). (why do you invert clauses order here ?)

You have a singleton Zs: ...,keepDuplicates(X, Y, [Z|Zs]),... and you should pay attention to that warning (of course, if your compiler display it), since it's often symptom of a true mistake.

Also, that predicate cannot cover all the cases: when X is not in Y, what do you associate to Z ?

To be true, I think you're doing it more complicated than required. Ignoring duplicates, the whole could be easy as

?- L1=[3,4,5,6],L2=[5,1,0,2,4],findall(C, (member(C,L1),memberchk(C,L2)), I).

Using Prolog to find Intersecting Lists

2 Answers2