Comparing a list with lists in another list in Prolog

Question

I have two lists:

L1 = [[a,b,c], [e,b,d], [f,g,a]]
L2 = [a,e]

I want to compare L2 with each list in L1 and find the number of common items. I am trying following code:

common([],L).
common([H|T], L, Out):-     
    intersection(H,L,Out), common(T, L, Out),
    length(Out,Len).

However, it is not working:

?- common([[a,b,c], [e,b,d], [f,g,a]], [a,e], Outlist).
false.

The main list remains list in list (as seen after debugging with writeln statements):

L is:
[a,e]
H|T is:
[[f,g,a]]
Outlist = [] .

Where is the problem and how can I correct this?

I edited the code to debug and found that somehow it has started working:

common([],L,Out).
common([H|T], L, Out):-     
    writeln('------------in common--------------'),
    writeln('L is:'), writeln(L),
    writeln('H is:'), writeln(H),
    intersection(L,H,Out2list),  
    writeln('Out2list is:'), writeln(Out2list),
    common(T, L, Out2).

41 ?- common([[a,b,c], [e,b,d], [f,g,a]], [a,e], Outlist).
------------in common--------------
L is:
[a,e]
H is:
[a,b,c]
Out2list is:
[a]
------------in common--------------
L is:
[a,e]
H is:
[e,b,d]
Out2list is:
[e]
------------in common--------------
L is:
[a,e]
H is:
[f,g,a]
Out2list is:
[a]
true.

I expect it to show [a], since that it common item and should come out in intersection. — rnso
[[f,g,a]] is a list of ONE ELEMENT, which is [f,g,a]. [a,e] is a list of TWO ELEMENTS, which are a and e. Clearly, these two lists do not have an element in common since {f,g,a] is not the same as either a or e. Therefore, intersection([a,e], [[f,g,a]], R) results in R = []. So your original problem is that you have lists of lists that you are intersecting with flat lists. [[f,g,a]] is a list of one element. [f,g,a] is a list of 3 elements. — lurker
I was trying to check [a,e] to each list in the larger list in common(). — rnso
You haven't shown what code actually writes out the first set of outputs you show, so that's a bit unclear. It's also unclear what output you are looking for in common. Do you just want it to succeed if it finds an intersection? That's all it currently does without the writeln statements. — lurker

tas tas · Accepted Answer · 2016-07-03T21:50:42

First let's observe that you have written a predicate common/2 and a predicate common/3. Reading your question, I assume you intend the former to be the base case for common/3. Thinking about the relation you want to describe, it would make sense to define that the intersection of the empty list and any other list is the empty list:

common([],_,[]).

However, it is not entirely clear what you expect the third argument to be. In your question you write that it should be the number of common items. The use of length/2 in your predicate common/3 supports this interpretation. In this case you want to have the lengths of the respective intersections in the third list:

common([],_,[]).
common([H|T], L, [Len|Out]):-   % Len is in the 3rd list
   intersection(H,L,I),         % I is intersection of H and L
   length(I,Len),               % Len is length of I
   common(T, L, Out).           % the same for T, L and Out

With this version your example query yields:

   ?- common([[a,b,c], [e,b,d], [f,g,a]],[a,e],I).
I = [1,1,1]

In your first comment however, you write that you want Outlist to be [a]. That suggests that you want lists instead of numbers in the third argument. But looking at your example query [a] can not be the answer. On the one hand, if you mean that you want to see all the intersections of the elements of the first list with the second argument, you might like to write something like:

common2([],_,[]).
common2([H|T], L, [I|Out]):-   % I is in the third list    
   intersection(H,L,I),        % I is intersection of H and L
   common2(T, L, Out).         % the same for T, L and Out

This yields with your example:

   ?- common2([[a,b,c], [e,b,d], [f,g,a]],[a,e],I).
I = [[a],[e],[a]]

On the other hand, if you mean that you want to see the intersection of all the lists of the first argument with the second argument, you might like to go with something like this:

common3([],_,[]).              % special case empty list
common3([H|T],L,I) :-          % if 1st list not empty
   common3_([H|T],L,I).        % I is described in common3_/3

common3_([],I,I).              % if the list is empty I = Outlist
common3_([H|T], L, O) :-
   intersection(H,L,I),        % I is intersection of H and L
   common3_(T,I,O).            % only the elements in I can be in O

With your example lists this yields

   ?- common3([[a,b,c], [e,b,d], [f,g,a]],[a,e],I).
I = []

since neither a nor e occur in all three lists. But if you add a to the second list:

   ?- common3([[a,b,c], [e,b,d,a], [f,g,a]],[a,e],I).
I = [a]

Comparing a list with lists in another list in Prolog

1 Answers