prolog predicate [sublist(Xs, Ys)]

Question

I am a new learner for prolog. Here is the question of our workshop, I have no idea where start it. Would really appreciate any help with this.

sublist(Xs, Ys)

This holds when Xs is a list containing some of the elements of Ys, in the same order they appear in the list Ys. This should work whenever Ys is a proper list. For example:

sublist([a,c,e],[a,b,c,d,e]) should succeed.

sublist([a,e,c],[a,b,c,d,e]) should fail.

sublist([a,X,d],[a,b,c,d,e]) should have the two solutions X=b and X=c.

sublist(X,[a,b,c]) should have the eight solutions X=[]; X=[c]; X=[b]; X=[b,c]; X=[a]; X=[a,c]; X=[a,b]; and X=[a,b,c].

Answer 1

My implementation:

sublist([], []).
sublist([H| Rest1], [H| Rest2]) :-sublist(Rest1, Rest2).
sublist(H, [_ | Rest2]) :-sublist(H, Rest2).

Examples:

?- sublist(X,[a,b,c]).
X = [a, b, c] ;
X = [a, b] ;
X = [a, c] ;
X = [a] ;
X = [b, c] ;
X = [b] ;
X = [c] ;
X = [].

?- sublist([a,c,e],[a,b,c,d,e]) .
true ;
false.

?- sublist([a,e,c],[a,b,c,d,e]) .
false.

?- sublist([a,X,d],[a,b,c,d,e]).
X = b ;
X = c ;
false.

Answer 2

Please note that a sublist needs its elements to be consecutive in the original list.

With that definition it would be easier to define a sublist through defining auxiliary predicates prefix and suffix, examples are taken from Shapiro's book:

prefix([], _).
prefix([X|Xs], [X,Ys]) :-
    prefix(Xs, Ys).

suffix(Xs, Xs).
suffix(Xs, [_|Ys]) :-
    suffix(Xs, Ys).

– and then it is just a matter of defining a sublist as either a suffix of a prefix:

sublist(Xs, Ys) :-
    prefix(Ps, Ys),
    suffix(Xs, Ps).

Result:

?- sublist(X, [1,2,3]).
X = [] ;
X = [1] ;
X = [] ;
X = [1, 2] ;
X = [2] ;
X = [] ;
X = [1, 2, 3] ;
X = [2, 3] ;
X = [3] ;
X = [] ;
false.

– or as a prefix of a suffix:

sublist(Xs, Ys) :-
    prefix(Xs, Ss),
    suffix(Ss, Ys).

Result:

?- sublist(X, [1,2,3]).
X = [] ;
X = [] ;
X = [] ;
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [2, 3] ;
X = [1, 2, 3] ;

But one could also do a recursive definition:

sublist(Xs, Ys) :-
    prefix(Xs, Ys).
sublist(Xs, [_|Ys]) :-
    sublist(Xs, Ys).

Result:

?- sublist(X, [1,2,3]).
X = [] ;
X = [1] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [] ;
X = [2] ;
X = [2, 3] ;
X = [] ;
X = [3] ;
X = [] ;
false.