Define a predicate in prolog

Question

Define 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. For example, 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].

My solution is like this:

sublist([],[]).
sublist([],[_|_]).
sublist([X|Xs],[Y|Ys]):- (
X=Y->sublist(Xs,Ys);
sublist([X|Xs],Ys)
).

However, it only outputs:

X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, c].

what's wrong with my solution?

You are using if-then-else, so it never tries the second conjunct. This would have been obvious if you had tried to trace. (The call X=Y will always succeed when either variable is uninstantiated). — Tomas By

damianodamiano damianodamiano · Accepted Answer · 2018-04-25T10:58:13

As said in the comment, the problem is in your if statement. You should rewrite your program like this:

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

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

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

BTW, sublist/2 is a built in predicate in SWI. You can look at that implementation wich is (taken from here):

sublist(L, L).
sublist(Sub, [H|T]) :-
    sublist_(T, H, Sub).

sublist_(Sub, _, Sub).
sublist_([H|T], _, Sub) :-
    sublist_(T, H, Sub).
sublist_([H|T], X, [X|Sub]) :-
    sublist_(T, H, Sub).

Define a predicate in prolog

1 Answers