0

I want to define a predicat p(X), where X is list of lists. p(X) is true, if in X there is only one element Y, that X and Y have no common elements.

This is not homework. This is a example problem for my exam. Thank you.

Mat
  • 202,337
  • 40
  • 393
  • 406
bpavlov
  • 1,080
  • 12
  • 32
  • 4
    Could you explain a bit more with examples? I try hard to get it. – Seçkin Savaşçı Aug 27 '12 at 11:58
  • I have problems with undestanding too. Maybe if X is a list of lists, then Y should be list, right? X = [ [1 2 3] [1 2 3 4] [2 3 5 6] [8 7] ], then Y is [ 8 7 ]. Y is the only one element in X and they has no common elems (exept 8 and 7, but they are only in Y)?! [1 2 3] has common elements - 1 2 3. [1 2 3 4] has common elements - 1 2 3, too. [ 2 3 5 ] has 2 and 3 as a common elements. I'm not sure if my logic is correct. – bpavlov Aug 27 '12 at 13:52
  • 1
    Let me rephrase it: p(x) must be true; if X is a list of lists AND all sublists of X except one must contain a common element. – Seçkin Savaşçı Aug 27 '12 at 14:28
  • As far as I understand the question, you're right. I just rewrite the requirement as it's writen on exam from 2009. – bpavlov Aug 27 '12 at 14:49

1 Answers1

1

Write it down:

p(X):-    %//  "define a predicate p(X), where X is list of lists, such that 
          %//   p(X) is true if in X there is only one element Y, 

  % findall( Y, (member(Y,X), ........ ), [_])

          %//   such that X and Y have no common elements".

    findall( Y, (member(Y,X), \+ have_common_element(X,Y) ), [_]).

have_common_element(A,B):- member(X,A), memberchk(X,B).

Now,

8 ?- p([[1,[2]],[2],[3]]). %// both [2] and [3] have no common elts w/ X
false.

9 ?- p([[1,[2]],[2]]).     %// [1,[2]] has one common elt w/ X, viz. [2]
true.

Prolog lists are heterogeneous. An element might be a list as well. And its element too.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • Hello, thank you for your reply. What is the difference between member and memberchk? ; ) – bpavlov Apr 19 '13 at 11:53
  • @bpavlov docs says, "Same as once(member(Elem, List))". I.e. it doesn't backtrack (fails on backtracking). I..e it is usually used to check whether a given element is a member of a list; calling `member` backtracks, i.e. generates more possibilities if they are there. In particular, calling `memberchk` with uninstantiated logvar as its first argument will just instantiate it to the first elem in list, once; but with `member` it will instantiate it to first, and then to all the rest, on backtracking. When we want just to check membership, we should use `memberchk`. – Will Ness Apr 22 '13 at 06:59