CODEWITHSUNDEEP
listprolog
Jimbo_ai
Jimbo_ai

Reputation: 167

Sublists in Prolog(without recognizing the empty list)

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!

Upvotes: 4

Views: 1245

Answers (2)

repeat
repeat

Reputation: 18726

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.

Upvotes: 3

user1812457
user1812457

Reputation:

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.

Upvotes: 4

Related Questions