Prolog: Create sublist, given two indices

4
votes

Basically, I need to create a predicate of the form sublist(S,M,N,L), where S is a new list formed from the elements of L between index M and index N, inclusive.

Here's where I've gotten:

sublist([],_,_,[]).
sublist([],M,N,_) :- (M > N).
sublist(S,M,N,L) :- sublist2(S,M,N,L,-1).
sublist2([H|T],St,En,[H2|T2],Idx) :-
   (Idx2 is Idx + 1,
   St =< Idx2,
   En >= Idx2,
   H = H2,
   sublist2(T,St,En,T2,Idx2);
   Idx2 is Idx + 1,
   sublist2(T,St,En,T2,Idx2)).

As with all my prolog problems, I feel I'm making it way more complicated than it should be. I've got the base cases right, but anything else evaluates to false. Any advice for this problem, and just general approach to prolog? I understand the language for the most part, but I can't seem to see the simple solutions.

2
prolog

2 Answers

1
votes

Simple solutions follow simple outlook. For lists it's recursion. Recursive programming is simple - just imagine you already have your function, following the given interface/requirements, and so you get to use it whenever you feel like it (but better, in the reduced cases).

sublist(S,M,N,[_A|B]):- M>0, M<N, sublist(S,M-1,N-1,B).

think of it as stating a law of sublists: sublist in a shorter list starts at decreased index.

sublist(S,M,N,[A|B]):- 0 is M, M<N, N2 is N-1, S=[A|D], sublist(D,0,N2,B).

and,

sublist([],0,0,_).

it is exclusive in the second index. tweak it. :)

1
votes

There is the possibility to handle indexing in a way similar to more traditional languages:

sublist(L, M, N, S) :-
    findall(E, (nth1(I, L, E), I >= M, I =< N), S).

or equivalently

sublist(L, M, N, S) :-
    findall(E, (between(M, N, I), nth1(I, L, E)), S).

nth1/3 is for indexing from 1, otherwise nth0/3 allows C style - start from 0. I've placed the sublist as last argument. It's a common convention in Prolog to place output parameters after input.

Here a (cumbersome) recursive definition

sublist(L,M,N,S) :- sublist2(1,L,M,N,S).

sublist2(_,[],_,_,[]).
sublist2(I,[X|Xs],M,N,[X|Ys]) :-
    between(M,N,I),
    J is I + 1,
    !, sublist2(J,Xs,M,N,Ys).
sublist2(I,[_|Xs],M,N,Ys) :-
    J is I + 1,
    sublist2(J,Xs,M,N,Ys).