The correct subset - Prolog

Question

I am trying to write a program that takes two lists as input and checks for the correct subset. I started with:

proper([A],[]). proper([],[A]). proper([A|T1],[A|T2]) :- proper(T1,T2). 

This works great for input in the same order. eg:

 ?- proper([a,b,c],[a,b,c,d]). Yes 

But not for input, for example:

 ?- proper([a,b,c],[b,d,a,c]). No 

After browsing the site, I found this previously asked question:

Subset Function in Prolog

This led me to modify my code as such:

 proper([A],[]). proper([],[A]). proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

This works fine for subsets, but not for the correct subsets. Which I think my problem arises from my understanding of how the second correct / 4 article works. Any help is appreciated.

Edit:

Implemented. I tried to determine if the first list was a suitable subset of the second, and the second was a correct subset of the first. Refine the code to be more accurate.

 proper([],_). proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

Answer 1

If I understood correctly, the first two declarations in your last attempt would mean that a list with 1 element is a correct subset of an empty list (false), and that an empty list is a proper subset of a list with one element (true); the first one should be problematic, because proper([1], []) will succeed, as well as proper([],[1]) , but the correct relation of the subset is asymmetric.

I believe that the reason your second attempt does not filter out identical subsets is because you do not have an declaration that requires A to be less than B.

Here are some possible solutions that I came up with. I use smaller_set/2 couple of times for more clarity and clarity.

 smaller_set(A, B) :- length(A, LA), length(B, LB), LA < LB. 

def_proper_subset/2 tries to capture the standard definition of a subset.

 def_proper_subset(A, B) :- smaller_set(A, B), % if A < B then there some _e in B that isn't in A. forall(member(_e, A), member(_e, B)). 

An example with a recursive definition, based on the removal of each corresponding element A and B. It ensures that A <B only with success if A runs through the elements to B.

 rec_proper_subset1([], [_|_]). rec_proper_subset1([_e|A], B) :- select(_e, B, C), % C is B with _e removed. Only true if _e is in B. rec_proper_subset1(A, C). 

In this case, the auxiliary attribute predicate is used to verify ownership as soon as the main predicate has already assured that A <B.

 rec_proper_subset2(A, B) :- smaller_set(A, B), rec_proper_subset2_(A, B). rec_proper_subset2_([], _). rec_proper_subset2_([_e|A], B) :- member(_e, B), rec_proper_subset2_(A, B). 

Edit:

• You need to use list_to_set/2 , sort/2 or something similar if you want to be sure that there are no duplicate elements in your lists. But such solutions will also work to find helper lists.
• I think def_proper_subset/2 is a kind of crappy solution, because it will only work to verify that A is a subset of B, but cannot generate a subset of B in A. The other two can be thought of.

(I screwed it and forgot to include the definition of land for rec_proper_subset2/2 , but now I fixed it).