Finding all the matching elements in 2 lists in prolog

Question

I have to write a Prolog program that finds all the matching elements between 2 separate lists. In practice it has to look like this:

?- intersect([a,c,a,b], [d,b,a,b], X).

X = [a,b]

What i have so far is this:

intersect([], Y, Z).
intersect([H| T1], Y, [H| T2]) :-
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :-
   intersect(T1, Y, T2).

(I had to make a remove_all function in a previous exercise. This removes all the elements from a list that match what you give)

This works except for one thing, my answer looks like this:

X = [a, b|_17660]

I'm new to Prolog and don't know that much about it. Why is there a "|_17660" at the end and how would i change my code to fix it? If someone could help me with this that would be appreciated.

Answer 1

First of all, you got three clean warnings about "singleton variables". That is a very clear hint that something went wrong. Usually, a Prolog programmer would fix that first. But of course, there are other ways, too.

So your problem is that you get X = [a, b|_17660] as an answer. What does this mean? The _176660 is just a variable name which has to be quantified universally. In other words the answer you got reads:

All X that start with [a, b|_] are a solution. Like [a, b] which is intended, but also ugly ones like [a, b|non_list]. Or even misleading or even incorrect ones like [a, b, c].

To understand where this problem comes from, lets focus on an implied ground query, like:

?- intersect([a,c,a,b], [d,b,a,b], [a,b|non_list]).
ERROR: Undefined procedure: remove_all/3

Argh, you did not show the definition of remove_all/3. In a traditional programming language, we would have to stop now. But in Prolog, we still can continue. No need to see that definition. I will instead use a specialization that no longer contains remove_all/3. So in a sense, this is only part of your program, but we can still draw conclusions from it. This is what I use:

intersect([], Y, Z) :- Z = non_list.
intersect([H| T1], Y, [H| T2]) :- false,
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :- T2 = non_list,
   intersect(T1, Y, T2).

This program is almost yours. Except that I have added extra goals to it. In another language this would not be possible. But in Prolog we can exploit a very nice property of (pure, monotonic) Prolog programs: You can add extra goals randomly and still predict what the outcome will be: The new program describes a subset of what your original program did. Of course, I had some suspicions, so my adding was somewhat guided. But you can always do the same with your buggy program!

Still not convinced? Now use that new program to see what you are actually describing:

?- intersect(Xs, Ys, Zs).
   Xs = [],
   Zs = non_list ...

?- intersect([], any, non_list).
   true.

Clearly, this is not what you intended. To see where that came from, we can specialize your program even more:

intersect([], Y, Z) :- Z = non_list.
intersect([H| T1], Y, [H| T2]) :- false,
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :- false,
   intersect(T1, Y, T2).

It should be evident by now, that the fact has to be specialized, otherwise these nonsensical solutions are possible. Here is such a specialization:

intersect([], _Y, Z) :-
   Z = [].
intersect([H| T1], Y, [H| T2]) :- false,
   member(H, Y),
   remove_all(H, T1, P),
   intersect(T1, Y, T2).
intersect([H| T1], Y, T2) :-
   intersect(T1, Y, T2).

The fact reads: The intersection of the empty list and anything is the empty list. Let's leave it that way, even if Y = non_list is now possible, too.

Your rule is still removed, since I have not seen your definition. It does not matter! I will continue to find problems in the remaining program. For the moment, I have no idea, where to look for problems. But I can ask Prolog to do this for me by asking the most general query which reads like

Prolog, just tell me all solutions you can describe.

(Remember this trick, you can always ask that question - without having even the slightest idea what the predicate is about.)

?- intersect(Xs, Ys, Zs).
   Xs = Zs, Zs = []
;  Xs = [_99922],
   Zs = [] ...

The first answer is perfect, but the second answer is not. Note that Ys does not occur anywhere, so the answer holds for all Ys. Even:

?- intersect([a], [a], []).
   true.

This problem is directly related to your rule, there is no condition for it whatsoever ...

See this for a clean solution.