Prolog - first list is sublist of second list while maintaining order?

Question

I want to check if elements of list L1 occur consecutively, and in the same order, in list L2.

For example - check([b,c],[a,b,c,d]) must return true while check([b,d],[a,b,c,d]) must return false

I looked at similar posts Prolog - first list is sublist of second list? and also tried out similar solutions but whenever i try to check if elements are present, i am unable to check if ordering is consecutive

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

and if i try to check if ordering is correct then my code is breaking.

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

Answer 1

Interesting problem! I'm surprised at how much code it took, so there may be a better solution than this.

First we need a helper to insist that a list is a prefix of another list. The base case is that we ran out of a prefix list; the inductive case is that the current items match and the remainder of both lists is a prefix match.

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

Now finding a consecutive sublist amounts to searching down a list for prefix matches. If the current items match, then having a prefix is a match:

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

Otherwise, we just discard this element of the search target and try again on the sublist:

consecutive_sublist(Prefix, [_|Ys]) :- consecutive_sublist(Prefix, Ys).