Sublists in Prolog(without recognizing the empty list)

4
votes

I want to create a predicate in Prolog which will check if a list A is a sublist of a list B. Moreover I do not want my program to consider an empty list as a subset of another one.

E.g. included_list([1,4],[1,2,3,4,5]). true. included_list([2,3],[1,2,3,4,5]). true. included_list([1,6],[1,2,3,4,5]). false. included_list([],[1,2,3,4,5]). false. and so on...

So, I have written the following code so far:

member(X,[X|Tail]).
member(X,[Head|Tail]):- member(X,Tail).

included_list([X],_).
included_list([Head|Tail],List):- member(Head,List), included_list(Tail,List).

But the above code seems to be wrong, because in one specific case it throws true, instead of throwing wrong. I wish I'd made it clear having presented the following screenshot:

some sample results

As you might have noticed the fifth(5th) sentence gives true, instead of wrong. That is, when I write a sentence of the form:

included_list([x,y],[w,x,v,z]).

whereas only x is included in the second list(and not y) the program gives me true(and this is wrong).

In general, if the first argument of the first list is included in the second list then, no matter if the rest of the former are included in the latter, the program gives me true.

In any other case the program gives me the right result(true or false).

What do I do wrong?

I will be waiting for your answers!

Thank you in advance!

2
listprolog
member/2 is ISO, so there is no need for you to define it yourself. And Prolog throws exceptions, not true or "wrong." - Daniel Lyons
In a first, it's your base case that is defective! You are saying included_list/2 is true for any one-item list. Instead say included_list([], _) and it will work just fine. - Daniel Lyons
I would be inclined to solve it with forall(member(X, Subset), member(X, List)) but I'm deeply annoyed that it does not generate! - Daniel Lyons
@DanielLyons This is what findall is for? forall is meant to be used for the side effect, and the fact that it does not create bindings is by design. - user1812457
@Boris Thanks! OTOH I'm having trouble finding the right formulation with findall/3. Do you see how to do it? - Daniel Lyons

2 Answers

4
votes

Your problem is the first clause of included_list/2. This:

included_list([X], _).

What does it mean? It means, "If the first argument is a list with one element, succeed, ignoring the second argument."

A short aside: if you would not ignore compiler warnings, you would have caught this mistake already. You should get a loud and clear "Singleton variable" warning, hinting that the code you have written does not do what you think it does.

What you actually mean is more along the lines of:

subset_list([X|Xs], Ys) :-
    subset_list_1(Xs, X, Ys).

subset_list_1([], X, Ys) :-
    member(X, Ys).
subset_list_1([X|Xs], X0, Ys) :-
    member(X0, Ys),
    subset_list_1(Xs, X, Ys).

But I don't know why you don't simply use the available subset/2, and simply add a requirement that the subset is not an empty list:

subset_list(Subset, List) :-
    Subset = [_|_], % a list with at least one element
    subset(Subset, List).

Despite what the documentation claims, the second argument to subset/2 does not have to be a true "set", but it does expect that both lists are ground (do not contain any free variables). You can see the source code here.

3
votes

In this answer we let maplist/2 handle recursion and define:

all_included(Sub, Es) :-
   same_length(Es, Xs),
   Sub = [_|_],                     % minimum length: 1
   append(_, Sub, Xs),              % maximum length: as long as `Es`
   maplist(list_member(Es), Sub).

Let's run the queries the OP gave! First up, use-cases we expect to succeed:

?- member(Xs, [[1,4],[2,3],[2,3,5],[3,4]]), all_included(Xs, [1,2,3,4,5]).
   Xs = [1,4]
;  Xs = [2,3]
;  Xs = [2,3,5]
;  Xs = [3,4]
;  false.

Next up, some use-cases we expect to fail:

?- member(Xs, [[],[2,6],[1,6]]), all_included(Xs, [1,2,3,4,5]).
false.

?- all_included([3,5], [1,2,5]).
false.