CODEWITHSUNDEEP
prologintersection
user3390252
user3390252

Reputation: 49

Using Prolog to find Intersecting Lists

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

Upvotes: 0

Views: 254

Answers (2)

repeat
repeat

Reputation: 18726

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.

Upvotes: 2

CapelliC
CapelliC

Reputation: 60014

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

Upvotes: 1

Related Questions