Sublist predicate in Prolog

Question

I am trying to define a predicate sublist(X,Y) in Prolog which is true when the elements of the list X all appear in the list Y, in the same order as they are in X.

My approach is to take the head of X, find the first instance of the head in Y and cut the list right before this first instance, then repeating this with the tail of X until the tail equals the empty list.

I have written the helper predicate cut(X,Y,Z) which is true if Z is the resulting list of cutting everything before the first instance of X in the list Y.

My code is as follows:

cut(_,[],[_|_]) :- false.
cut(X,[H|T],[H|T]) :- X = H, !.
cut(X,[_|T],Y) :- cut(X,T,Y).

sublist([],[]).
sublist([],[_|_]).
sublist([A|B],C) :- cut(A,C,Z), sublist(B,Z).

When I query

?- sublist(L,[1,2,3]).

Instead of giving all sublists of [1,2,3] Prolog gives me the following output:

L = [] ;
L = [1] ;
L = [1, 1] ;
L = [1, 1, 1] ;
L = [1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...] ;
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...]

I fail to see my mistake. Can anyone point it out to me?

You don't need the rule cut(_,[],[_|_]) :- false. Just its absence will cause queries that look like cut(_,[],[_|_]). to fail since it doesn't match a succeeding rule. And did you try doing a trace? Or did you try just testing cut/3 itself? Is there a reason you're creating cut/3 and not just using select/3? — lurker

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2017-03-22T13:40:58

Short answer: cut/3 does not pop from the list if it finds an element.

The first answer L = []. is the result of the second clause firing. Now the next answer is generated by the last clause. So what happens is:

sublist(A,[1,2,3]) :- % C = [1,2,3]
    cut([A|B],[1,2,3],[H|T]) :- % H = 1, T = [2,3], Z = [1,2,3]
        A = H, % A=1
        !.
    sublist(B,[1,2,3]).

So since the second clause of cut/3 fires, the second and third argument are equivalent and thus cut/3 does not "pop" from the list.

A way to solve this and guarantee progression is popping from the list, with:

cut(_,[],[_|_]) :- false.
cut(H,[H|T],T) :-
    !.
cut(X,[_|T],Y) :-
    cut(X,T,Y).

(I also took the liberty to replace X with H in the head of the clause making it more elegant). Now it generates:

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

Note that the answer does not generate all lists: for instance L = [2,3] is also a valid answer. The reason this does not work is because cut/3 has ! and thus does not allow to introduce additional elements. You can solve this with:

cut(_,[],[_|_]) :- false.
cut(H,[H|T],T).
cut(X,[_|T],Y) :-
    cut(X,T,Y).

Now we obtain:

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

Nevertheless you can solve the problem quite elegantly without using a help predicate at all. We can first construct a predicate that validates/creates lists:

list([]).
list([_|T]) :-
    list(T).

Next we state that if X is empty, you do not really care what sort of list is at the right:

sublist([],L) :-
    list(L).

And finally if X is not empty, we need to obtain HX (the head of X) somewhere. If we find it, we can either decide to "accept" it, and pop both lists, or we can decide to look for another HX, like:

sublist([HX|TX],[HX|TY]) :-
    sublist(TX,TY).
sublist(X,[_|TY]) :-
    X = [_|_],
    sublist(X,TY).

The X = [_|_] in the last clause in not strictly necessary, but prevents generating duplicate results with the sublist([],X) clause.

Or putting it together:

list([]).
list([_|T]) :-
    list(T).

sublist([],L) :-
    list(L).
sublist([HX|TX],[HX|TY]) :-
    sublist(TX,TY).
sublist(X,[_|TY]) :-
    X = [_|_],
    sublist(X,TY).

This generates:

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

Or:

?- sublist([1,2,3],L).
L = [1, 2, 3] ;
L = [1, 2, 3, _G2440] ;
L = [1, 2, 3, _G2440, _G2443] ;
L = [1, 2, 3, _G2440, _G2443, _G2446] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452, _G2455] ;
L = [1, 2, 3, _G2440, _G2443, _G2446, _G2449, _G2452, _G2455|...] ;

Or:

?- sublist([1,2,3],[1,2,4,5,3,6]).
true ;

Sublist predicate in Prolog

1 Answers