Finding an intersection in Prolog using list predicates

Question

I'm really new to Prolog and I am trying to make an isIntersection that gives me the intersection of two lists and puts the answer in the third list. I cannot use any Prolog list predicates because it's for a class and that's just the rules. This is what I have and I'm having trouble debugging and seeing why this implementation is wrong. Anyone have any ideas?

/* Checks if the item is in the list */
in(Item, [Item|Rest]).
in(Item, [Not|Rest]) :- in(Item, Rest).

/* Makes the intersection list */
isIntersection([], [], []).
isIntersection([H|R], List, [H|Final]) :-
   in(H, List),
   isIntersection(R, List, Final),
   write(H).
isIntersection([Discard|Rest], List, Final) :-
   isIntersection(Rest, List, Final),
   write(Discard).

Answer 1

Prolog is a very versatile query language, so let's use Prolog to find the problem!

?- isIntersection([a,b],[c,b],Zs).
false.

This failure is not what we expect. To better localize the problem we might a) generalize the query or b) reduce input size. I will try generalizing it first:

?- isIntersection([a,b],Ys,Zs).
ERROR: Out of global stack

Seems we have no luck, but then this query would have to produce infinitely many lists for Ys so it might be OK to loop.

I could continue that way, but why not let Prolog do the thinking for me? I will try all possible lists:

?- length(L,_),append(Xs,Ys,L), isIntersection(Xs,Ys,Zs).
L = Xs, Xs = Ys, Ys = Zs, Zs = [] ;
L = Xs, Xs = [_G682],
Ys = Zs, Zs = [] ;
L = Xs, Xs = [_G682, _G685],
Ys = Zs, Zs = [] ;
L = Xs, Xs = [_G682, _G685, _G688],
Ys = Zs, Zs = [] ;
L = Xs, Xs = [_G682, _G685, _G688, _G691],
Ys = Zs, Zs = [] ...

So for each list length (so far), there is only one solution with Ys and Zs being an empty list... Is there any solution for Ys being larger?

?- length(L,_),Ys = [_|_], append(Xs,Ys,L), isIntersection(Xs,Ys,Zs).
LOOPS

So lets take the minimal missing example from above with Ys having one element:

?- isIntersection([],[a],[]).
false.

With this goal, now look at your code!

But there is another problem (after fixing above):

?- isIntersection([a],[a],Xs).
Xs = [a] ;
Xs = [].

The rule discards any element! But it should only discard those that are not in List. So:

isIntersection([Discard|Rest], List, Final) :-
   list_without(List,Discard), % maplist(dif(Discard),List)
   isIntersection(Rest, List, Final).

list_without([], _).
list_without([E|Es], F) :-
   dif(E, F),
   list_without(Es, F).

Finally, always keep an eye on negative examples. Many attempts here (incorrectly) succeeds for queries like isIntersection([a],[a],[]).

(Your relation in/2 might better be called element_in/2)

Answer 2

there is only a List that can match your base case, and this simple fact inhibits the whole computation.

Answer 3

I'd go at it something like this, sorting and merging so as to avoid the O(n²) performance:

intersection_of( Xs , Ys , Zs ) :-     % to find the intersection of two sets, we
  sort(Xs,X1)     ,                    % - sort the left  source list, removing duplicates to ensure that it's a set
  sort(Ys,Y1)     ,                    % - sort the right source list, removing duplicates to ensure that it's a set
  merge(Xs,Ys,Z1) ,                    % - merge them to find the common members (an ordered set)
  ( var(Zs) ->                         % - if the result is unbound,
    Zs = Z1 ;                          %   - simply unify the merge result with the result set
    sort(Zs,Z1)                        %   - otherwise, sort the result and match against the merge result
  ) .                                  %

The merge is simple

merge( []     , []     , []     ) .
merge( [_|_]  , []     , []     ) .
merge( []     , [_|_]  , []     ) .
merge( [X|Xs] , [Y|Ys] , [Z|Zs] ) :- X =  Y , merge(   Xs  ,    Ys  , Zs ) .
merge( [X|Xs] , [Y|Ys] ,    Zs  ) :- X @< Y , merge(   Xs  , [Y|Ys] , Zs ) .
merge( [X|Xs] , [Y|Ys] ,    Zs  ) :- X @> Y , merge([X|Xs] ,    Ys  , Zs ) .