3

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.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
ccdavid
  • 31
  • 1
  • 1
  • 2

5 Answers5

3

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.

nedned
  • 3,552
  • 8
  • 38
  • 41
1

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.
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
  • 2
    The original version using member/2 is still very appealing. Isn't there a better way to solve this? I particularly do not like that one has to understand recursion. Also this asymmetry between the two lists might be eliminated. – false Jun 23 '15 at 00:10
1

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.

lefunction
  • 301
  • 2
  • 16
  • 1
    Rule-of-thumb: Mixing `dif/2` and `(\+)/1` most probably won't work: `Y=a,doesIntersect([b,Y],[b]).` correctly succeeds, but `doesIntersect([b,Y],[b]),Y=a.` fails. So your program is not a relation. – false Jun 23 '15 at 14:19
0

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.

Yasel
  • 2,920
  • 4
  • 40
  • 48
  • 2
    `common_memberd([1],[X]), X=2.` succeeds, but `X=2, common_memberd([1],[X]).` fails. – false Jun 23 '15 at 01:05
  • Good point, it occurs to me a new solution, using recursion, but still fails for `common_memberd([X,Y, 1],[2,Z, 3]).` – Yasel Jun 23 '15 at 03:19
  • 2
    You can either add a check for, say, groundness, i.e. `( ground(T+Q) -> true ; throw(error(instantiation_error,_)) )`, or use @repeat's approach ; or something in between using [`iso_dif/2`](http://stackoverflow.com/a/20238931/772868) which also produces an `instantiation_error` in situations where terms are insufficiently instantiated. – false Jun 23 '15 at 10:41
  • 1
    And `not/1` is **not** frequently supported, it's rather `(\+)/1` – false Jun 23 '15 at 10:45
-1

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.
Juanjo Conti
  • 28,823
  • 42
  • 111
  • 133