CODEWITHSUNDEEP
listprolog
ccdavid
ccdavid

Reputation: 31

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

How to determine whether two list have same element in prolog? If i have two list A and B, i want to know whether they have the same element.

Upvotes: 3

Views: 10659

Answers (5)

repeat
repeat

Reputation: 18726

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.

Upvotes: 2

lefunction
lefunction

Reputation: 301

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.

Upvotes: 1

Yasel
Yasel

Reputation: 3120

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.

Upvotes: 0

Juanjo Conti
Juanjo Conti

Reputation: 30013

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.

Upvotes: -1

nedned
nedned

Reputation: 3707

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.

Upvotes: 3

Related Questions