Prolog: Compare 2 Lists and find out if at least one member of the first list exists in the other one

Question

In the quest of learning more about prolog (and in the interest of solving my assignment), I have come across a situation where I need to compare 2 lists and find out if AT LEAST ONE element match ...
Here is an example what I want to do:

?-match([a,b,c],[x,y,z]).
no.

?-match([a,b,c],[x,y,b]).
yes.

My solution up to now:

compare_list([],[]).
compare_list([],_).
compare_list([L1Head|L1Tail],List2):-
    member(L1Head,List2),
    compare_list(L1Tail,List2).

but this solution gives a true when all the members of List1 are present in List2!

Please people, don't think that I am cheating on an assignment, the problem is much much more complex, I am just stuck at this point and need help to get out of this sticky corner... otherwise I have done the entire assignment myself!

Solution 1

I'll comment on the attempt you've made, which is close, but not quite there:

compare_list([],[]).
compare_list([],_).

The first clause for compare_list/2 says that the empty list has at least one element in the empty list. The second says the empty list has at least one element in any other list. So the first clause is redundant (it's already covered by the second). Whether you want this to be true (that an empty list has an element in any other list) is up to you. Since an empty list has no members, one might consider this a failure case (and, thus, not be declared as true) but you can call it true by definition if you wish. However, it will cause some issues in the recursive case once you have your predicate correctly defined since reducing down to [] will become true and ultimately it might find any list has elements in any list (oops!). I'd leave these two clauses out and consider this case a fail.

compare_list([L1Head|L1Tail], List2):-
    member(L1Head, List2),
    compare_list(L1Tail, List2).

This says that the first list has an element in the second list if: (1) the head of the list is a member of the second list, AND (2) the tail of the first list has an element in the second list. Does this sound logically correct? If you think this through, given there are no additional compare_list/2 clauses, this is true only if EVERY element of the first list is a member of the second list, as you have observed.

Finally, you're missing the case where the first list has a head that is not a member of the second list. This shouldn't necessarily be a failure since the tail of the first list may have a member in the second list, even if the first element (head) is not a member.

Solution 2

your problem can be solved using the simpler builtins

match(L1,L2) :- member(E,L1),member(E,L2). % full join

add the nasty cut if you are really interested only in 'at least one' solution

match(L1,L2) :- member(E,L1),memberchk(E,L2),!. % really, just the first!

Solution 3

Using your example predicate match/2. The solution is as simple as traverse recursively the List1 (on the left) and check if the Head belongs to the List2 via the memberchk/2 predicate. The reason to use memberchk/2 is that it succeeds only once (i.e., not re-executable on backtracking) and this is what your "AT LEAST ONE" condition states. If the List1 is empty, the predicate fails.

Code:

match([Head|Tail], List2):-
        memberchk(Head,List2).
match([_|Tail],List2):-
        match(Tail,List2).

Examples:

| ?-  match([a,b,c],[x,y,z]).
no

| ?-  match([a,b,c],[x,y,b]).
yes

| ?-  match([a,b,c],[]).     
no

| ?-  match([],[x,y,b]).
no

Solution 4

Another way is to use nth0 predicate.

match(L1, L2) :-
    nth0(_, L1, SharedItem),
    nth0(_, L2, SharedItem).

The first nth0 says "is there a L1 list item with index '_' (ie don't care whether it is in first, second etc. position in the list), whose name is variable SharedItem.

The second nth0 does the same for L2.

But the nice trick is in the unification.. by using the same variable name SharedItem on both nth's, prolog will continue iterating through the lists until the same item is in both.

As always the 'trace.' predicate is your best friend.. run it before calling the above to see what prolog is doing in the background:

[trace]  ?- match([a,b,c],[x,y,b]).
   Call: (6) match([a, b, c], [x, y, b]) ? creep
   Call: (7) lists:nth0(_G1965, [a, b, c], _G1967) ? creep
   Exit: (7) lists:nth0(0, [a, b, c], a) ? creep
   Call: (7) lists:nth0(_G1968, [x, y, b], a) ? creep
   Fail: (7) lists:nth0(_G1968, [x, y, b], a) ? creep
   Redo: (7) lists:nth0(_G1968, [a, b, c], _G1970) ? creep
   Exit: (7) lists:nth0(1, [a, b, c], b) ? creep
   Call: (7) lists:nth0(_G1968, [x, y, b], b) ? creep
   Exit: (7) lists:nth0(2, [x, y, b], b) ? creep
   Exit: (6) match([a, b, c], [x, y, b]) ? creep
true .

So the 'outer' loop is L1.. it first tries index 0 of L1(a), then when it fails to find it in L2, it does a Redo (of the first nth0), but this time with index 1(b), and finds it, then returns true.

View more solutions