How to determine whether two list have same element in prolog?

How to determine whether t开发者_开发问答wo list have same element in prolog? If i have two list A and B, i want to know whether they have the same element.

---

You need to write a predicate. You'll probably find the prolog builtin member/2 useful.

It's hard to say any more without giving the answer. Just think about it for a bit. You'll get it.

---

How about using intersection/3?

doesIntersect(X,Y) :-
    intersection(X,Y,Z),
    dif(Z,[]).

If intersection/3 produces an empty list then the lists have nothing in common and the result is false.

intersection/3 calls member/2 recursively:

intersection([X|Tail],Y,[X|Z]) :-
    member(X,Y),
    intersection(Tail,Y,Z).
intersection([X|Tail],Y,Z) :-
    \+ member(X,Y),
    intersection(Tail,Y,Z).
intersection([],_,[]).

source.

---

We start with a pure implementation based on the builtin predicate member/2:

common_member(Xs,Ys) :-
   member(E,Xs),
   member(E,Ys).

Sample queries:

?- common_member([1,2,3],[1]).
  true
; false.

?- common_member([1,2,3],[4]).
false.

?- common_member([1,2,3],[2,3,1]).
  true
; true
; true
; false.

Declaratively, above code is okay. However, it leaves behind useless choicepoints when succeeding. Also, we get redundant answers if there is more than one item present in both lists.

Can we improve above efficiency aspects while remaining logically pure? Yes!

But how? By using if_/3 together with the reified test predicate memberd_t/3!

common_memberd([X|Xs],Ys) :-
   if_(memberd_t(X,Ys), true, common_memberd(Xs,Ys)).

Let's run above sample queries again, this time with common_memberd/2:

?- common_memberd([1,2,3],[1]).
true.

?- common_memberd([1,2,3],[4]).
false.

?- common_memberd([1,2,3],[2,3,1]).
true.

Redundant answers have been eliminated and the succeeding queries do so deterministically.

Note that common_memberd/2 is pure, so we get sound answers even for quite general queries!

?- common_memberd([1,2,3],[A,B]).
      A=1
; dif(A,1),                         B=1
;               A=2 ,           dif(B,1)
; dif(A,1), dif(A,2),                         B=2
;                         A=3 , dif(B,1), dif(B,2)
; dif(A,1), dif(A,2), dif(A,3),                     B=3
; false.

---

You can start by building a predicate differs/2 that verify if any of the elements on the list A is not member of the list B. If you can find an element on A that fulfill this condition, then you can affirm that A is not contained in B. This is actually easier that try to verify that every element of A is present in B.
Using the build-in predicate member/2, the differs/2 will look like this:

differs(T, Q):- 
         member(X,T), 
         not( member(X, Q)). 

Now to prove that both list contains the same elements, you just need to verify that they don't differs. Using the same predicate name used by @repeat (curious, who is repeat now?), this is my common_memberd\2 predicate:

common_memberd(T, Q):- 
                not( differs(T, Q)), 
                not( differs(Q, T)).

Consult:

?- common_memberd( [2,3,4,1], [3, 1,4,2]).  
   true.  
?- common_memberd( [2,3,1,5], [3, 1,4,2]).  
   false.

Note: This solution works regardless the element's order or either they are duplicated or not.

---

Let me know if this is what you where looking for:

same(T, Q) :- any(T, Q), !; any(Q, T), !.

any([X|_], [X,_]):- !.
any([X|T], Q) :- member(X, Q), !; any(T, Q), !.

If you consult it:

?- same([1,2,3,4], [3]).
true.

?- same([1,2,3,4], [4]).
true.

?- same([1], [1,4]).
true.

?- same([1,4], [1]).
true.