% CPSC 312
% Author: Steven Wolfman
% Released into the public domain

% sublist(List1, List2) is true when List1 and List2 are lists such 
% that all elements in List1 are also elements of List2, in the same order
% (and the same count of elements, e.g., if List1 is [1,1], then List2 cannot
% be [1]).
sublist([], []).
sublist([X|Xs], [X|Ys]) :- sublist(Xs, Ys).
sublist(List1, [_|List2]) :- sublist(List1, List2).


% NOTE: If our base case is sublist([], _)., then we can discover that [] is a sublist of a
% non-empty list either via the base case or via the third clause stripping away an element.
% So, the more general base case gives us repeated answers.