Sublists in Prolog(without recognizing the empty list)

Question

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:

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!

`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, Dec 11 '15 at 00:33
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, Dec 11 '15 at 05:41
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, Dec 11 '15 at 05:57
@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. — , Dec 11 '15 at 08:44
@Boris Thanks! OTOH I'm having trouble finding the right formulation with `findall/3`. Do you see how to do it? — Daniel Lyons, Dec 11 '15 at 16:32
@DanielLyons `findall(X, ( member(X, Subset), member(X, List) ), Subset)` or `foreach(member(X, Subset), member(X, List))`. But I really wouldn't use either. — , Dec 12 '15 at 14:16

score 4 · Accepted Answer · answered Dec 11 '15 at 08:59

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.

score 3 · Answer 2 · edited May 23 '17 at 12:07

In this answer we let meta-predicate 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.

Sublists in Prolog(without recognizing the empty list)

2 Answers2