Proper Subset - Prolog

Question

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

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

This works perfectly fine for inputs in the exact same order. for instance:

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

But doesn't for inputs such as:

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

After looking through the site I found this previously asked question:

Subset function in prolog

Which lead 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 proper subsets. Which I think my problem is arising from my understanding of how the second clause of proper/4 works. Any and all help is greatly appreciated.

Edit:

Realized I was trying to determine if the first list was a proper subset of the second and the second was a proper subset of the first. Cleaned up the code to be more precise.

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

Just sort your lists. This is the most sensible thing to do, and how the standard library deals with it, too. — user1812457
@Boris could you point me towards the standard library predicate for proper subsets? — Shon
@aBathologist Take a look at library(ordsets) (In the SWI-Prolog implementation, for example) and its source. There is no predicate for "proper" subset, but just looking at the lengths should be good enough, as you already pointed out in your answer. — user1812457
@aBathologist My point was mainly that the only sensible way to deal with the concept of a "set" when it is represented as a Prolog list is to keep the list sorted. Lists are nested terms that can be traversed in only one direction. — user1812457
@Boris I see! That is an important point to make. I just thought I had been overlooking a library or that there was a particular way of using sort to accomplish proper subset checks that I couldn't quite fathom. Thanks for the elaboration. — Shon

Shon Shon · Accepted Answer · 2013-10-24T21:11:32

If I understand correctly, the first two declarations in your last attempt would mean that, both a list with 1 element is a proper 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 proper subset relation is asymmetric.

I believe the reason that your second attempt doesn't filter out identical subsets is that you have no declaration that requires A to be smaller than B.

Here are some possible solutions I came up with. I use smaller_set/2 a couple times for increased clarity and concision.

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's some _e in B that isn't in A.
    forall(member(_e, A), member(_e, B)).

An example with recursive definition, based on removeing each matching element of A and B. It assures that A < B by only succeeding if A runs out of elements before 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).

This one uses an auxiliarry predicate to check membership once 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'll need to use list_to_set/2, sort/2, or something similar if you want to be sure that your lists don't have any duplicate elements. But these kinds of solutions will also work to find sub lists.
I think def_proper_subset/2 is a kind of crappy solution, because it will only work to check that A is a subset of B but can't generate a subset of B in A. The other two are able to thought.

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

Proper Subset - Prolog

1 Answers