CODEWITHSUNDEEP
listrecursionprolog
user893182
user893182

Reputation: 97

Prolog - first list is sublist of second list?

For example:

isin([1,2,3], [1,0,1,2,3,0])

will yield true because 123 is inside of 101230

I wrote the following code:

isin([AH|AT],[AH|AT]).

isin([AH|AT],[BH|BT]):- AH = BH, isin(AT,BT), isin([AH|AT],BT).

seems not working. Try not to use any built-in functions and BTW, Prolog has a built-in sublist(L1, L2) function.

How do I write a query against a built-in function using SWI-Prolog ? I tried to directly write:

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

but it returns an undefined procedure error.

Also, is it possible to see how a built-in function is coded and how ?

Upvotes: 6

Views: 32094

Answers (8)

Mihai Danila
Mihai Danila

Reputation: 2348

% prefix: Is the first list the prefix of the second?
% True if the two have the same head and the tail of the first
% is the prefix of the tail of the second.
prefix([X|T], [X|R]) :- prefix(T, R).
% True if the first list is the empty list.
prefix([], _).

% sublist: Is the first list a sublist of the second list?
% True if the two lists start with the same element and
% the tail of the first is a prefix of the tail of the second.
sublist([X|T], [X|R]) :- prefix(T, R), !.
% True if the first list is a sublist of the tail of the second.
sublist(L, [_|R]) :- sublist(L, R).
% True if the first list is the empty list.
sublist([], _).

Upvotes: 0

Karthik_D
Karthik_D

Reputation: 3

With a few modifications to ДМИТРИЙ МАЛИКОВ's answer, this is something that works,

preList([], L).
preList([H_s|T_s], [H_s|Tail]):-
    preList(T_s, Tail).

subList([H_s|T_s], [H_s|Tail]):-
    preList(T_s, Tail).

subList([H_s|T_s], [H_s|Tail]):-
    subList([H_s|T_s], Tail).
    
subList(Sub, [_|Tail]):-
    subList(Sub, Tail).

Essentially, look for a match between the first elements of the sub-list and the main-list using the subList procedure. When a match occurs, head over to the preList procedure and check if this turns out to be a prefix for the remainder of the list. If so, the resolution ends in success.

If not, come back and continue comparing the remainder of the list for a first-element match.

Upvotes: 0

Klajdi Isteri
Klajdi Isteri

Reputation: 1

sublist([],[],_):-!.
sublist(_,[],_):-!.

sublist([H1|T1],[H2|T2],LV):-
H1 = H2,!,
sublist(T1,T2,LV).

sublist([H1|T1],[H2|_],LV):-
not(H1 = H2),
sublist(T1,LV,LV).

If you try these queries:

?-sublist([1,2,3,4,5],[1,2,3],[1,2,3]).
TRUE

?-sublist([1,2,3,4,5],[1,2,4],[1,2,4]).
FALSE

Upvotes: 0

Parsa
Parsa

Reputation: 73

sublist(S, L) :-length(S, N),
                length(L, N1),
                N2 is N1 - N,
                length(P, N2),
                append( _ , S, P), 
                append(P, _ , L).

to avoid stack overflow for failing cases we must determine the size of the list P.

Upvotes: 0

guilieen
guilieen

Reputation: 150

another implementation using member is : 

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

member/2 returns true if find the element in a list

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

Upvotes: 1

Kaitain
Kaitain

Reputation: 960

If you want 

my_sublist( [2,3,4], [1,2,3,4,5] )

...to succeed, but

my_sublist( [1,3,5], [1,2,3,4,5] )

...to fail, you might want to consider

my_sublist( Sublist, List ) :-
    append( [_, Sublist, _], List ).

Note that if you pass a variable through as Sublist, backtracking will give you a comprehensive set of all possible sublists of List, but this will in general include several repeats of the empty list (because the empty list can combine with all other sublists both ahead and behind of them in an append operation).

Upvotes: 2

ДМИТРИЙ МАЛИКОВ
ДМИТРИЙ МАЛИКОВ

Reputation: 21972

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

Upvotes: 11

starblue
starblue

Reputation: 56752

Since it seems to be homework I will only give you a few hints:

  • It seems you are missing the case where an empty list is a sublist of the other one.

  • You mixed the two cases "the sublist starts here" and "the sublist starts later" into one clause.

  • It seems the elements of the sublist should be consecutive in the larger list. For that you need two predicates. Essentially you have to remember that the sublist has started when you take apart the lists.

There is no builtin sublist/2, only a sublist/3 which does something different (filter list with a predicate).

Upvotes: 1

Related Questions