CODEWITHSUNDEEP
prolog
rnso
rnso

Reputation: 24535

Comparing a list with lists in another list in Prolog

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.

Upvotes: 1

Views: 856

Answers (1)

tas
tas

Reputation: 8140

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]

Upvotes: 1

Related Questions