CODEWITHSUNDEEP
prologsublist
Crownless
Crownless

Reputation: 133

How to check if a list is a non-empty sublist of another list in Prolog

I am trying to create an included_list(X,Y) term that checks if X is a non-empty sublist of Y.

I already use this for checking if the elements exist on the Y list 

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

And the append term

append([], L, L).
append([X | L1], L2, [X | L3]) :- append(L1, L2, L3).

to create a list, in order for the program to finish on 

included_list([HeadX|TailX],[HeadX|TailX]).

but I am having problems handling the new empty list that I am trying to create through "append" (I want to create an empty list to add elements that are confirmed to exist on both lists.)

I have found this 

sublist1( [], _ ).
sublist1( [X|XS], [X|XSS] ) :- sublist1( XS, XSS ).
sublist1( [X|XS], [_|XSS] ) :- sublist1( [X|XS], XSS ).

but it turns true on sublist([],[1,2,3,4)

Upvotes: 4

Views: 2953

Answers (5)

Tacho Jelev
Tacho Jelev

Reputation: 1

Basically we can check if M is a sublist of L if M exists in L by appending something on its back and/or its front.

append([], Y, Y).
append([X|XS],YS,[X|Res]) :- append(XS, YS, Res).

sublist(_, []).
sublist(L, M) :- append(R, _, L), append(_, M, R).

Upvotes: 0

lurker
lurker

Reputation: 58234

Since you're looking for a non-contiguous sublist or ordered subset, and not wanting to include the empty list, then:

sub_list([X], [X|_]).
sub_list([X], [Y|T]) :-
    X \== Y,
    sub_list([X], T).
sub_list([X,Y|T1], [X|T2]) :-
    sub_list([Y|T1], T2).
sub_list([X,Y|T1], [Z|T2]) :-
    X \== Z,
    sub_list([X,Y|T1], T2).

Some results:

| ?- sub_list([1,4], [1,2,3,4]).

true ? a

no
| ?- sub_list(X, [1,2,3]).

X = [1] ? a

X = [2]

X = [3]

X = [1,2]

X = [1,3]

X = [1,2,3]

X = [2,3]

(2 ms) no
| ?- sub_list([1,X], [1,2,3,4]).

X = 2 ? a

X = 3

X = 4

(2 ms) no

Note that it doesn't just tell you if one list is a sublist of another, but it answers more general questions of, for example, What are the sublists of L? When cuts are used in predicates, it can remove possible valid solutions in that case. So this solution avoids the use of cut for this reason.

Explanation:

The idea is to generate a set of rules which define what a sublist is and try to do so without being procedural or imperative. The above clauses can be interpreted as:

  1. [X] is a sublist of the list [X|_]
  2. [X] is a sublist of the list [Y|T] if X and Y are different and [X] is a sublist of the list T. The condition of X and Y different prevents this rule from overlapping with rule #1 and greatly reduces the number of inferences required to execute the query by avoiding unnecessary recursions.
  3. [X,Y|T1] is a sublist of [X|T2] if [Y|T1] is a sublist of T2. The form [X,Y|T1] ensures that the list has at least two elements so as not to overlap with rule #1 (which can result in any single solution being repeated more than once).
  4. [X,Y|T1] is a sublist of [Z|T2] if X and Z are different and [X,Y|T1] is a sublist of T2. The form [X,Y|T1] ensures that the list has at least two elements so as not to overlap with rule #2, and the condition of X and Z different prevents this rule from overlapping with rule #3 (which can result in any single solution being repeated more than once) and greatly reduces the number of inferences required to execute the query by avoiding unnecessary recursions.

Upvotes: 5

joel76
joel76

Reputation: 5615

I would use append :

sublist(X, []) :-
    is_list(X).


sublist(L, [X | Rest]) :-
    append(_, [X|T], L),
    sublist(T, Rest).

Upvotes: 0

user2520215
user2520215

Reputation: 653

Here is what you an do:

mysublist(L,L1):- sublist(L,L1), notnull(L).

notnull(X):-X\=[].

sublist( [], _ ).
sublist( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).
sublist( [X|XS], [_|XSS] ) :- sublist( [X|XS], XSS ).

Taking a reference from this: Prolog - first list is sublist of second list? I just added the condition to check if it was empty beforehand.

Hope this helps.

Upvotes: 1

levi
levi

Reputation: 22697

If order matters. Example [1,2,3] is sublist of [1,2,3,4] but [1,3,2] not.

You can do something like this. 

sublist([],L).
sublist([X|L1],[X|L2]):- sublist(L1,L2)

Upvotes: 0

Related Questions