Search code examples
prologdcg

prolog - sublist of list - alternative approach

I implemented function to get sublist of list, for example: 

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

sublist([1,2,4], [1,2,3,4,5,1,2,6]). false look at my solution: 

my_equals([], _).
my_equals([H1|T1], [H1|T2]) :- my_equals(T1, T2).

sublist([], _).
sublist(L1, [H2|T2]) :- my_equals(L1, [H2|T2]); sublist(L1, T2).

Could you give me another solution ? Maybe there is exists some predefined predicate as my_equals ?

Solution

  • There's also a DCG approach to the problem:

    substr(Sub) --> seq(_), seq(Sub), seq(_).

seq([]) --> [].
seq([Next|Rest]) --> [Next], seq(Rest).

    Which you would call with:

    phrase(substr([1,2,4]), [1,2,3,4,5,1,2,4,6]).

    You can define:

    sublist(Sub, List) :-
    phrase(substr(Sub), List).

    So you could call it by, sublist([1,2,4], [1,2,3,4,5,1,2,4,6])..

    Per @mat's suggestion:

    substr(Sub) --> ..., seq(Sub), ... .

... --> [] | [_], ... .

    Yes, you can have a predicate named .... :)

    Per suggestions from @repeat and @false, I changed the name from subseq (subsequence) to substr (substring) since the meaning of "subsequence" embraces non-contiguous sequences.