Prolog: Create sublist, given two indices

Question

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.

Will Ness · Accepted Answer · 2013-05-07T19:56:44.827

1

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. :)

edited May 07 '13 at 19:56

answered May 07 '13 at 19:48

Will Ness

70,110
9
98
181

what does the wildcard in front of the A mean? – Adam Duvall May 08 '13 at 03:21
3

@AdamDuvall If you mean the underscore `_`, it tells prolog to ignore the variable. You can use just an underscore by itself, but an underscore with a name is more descriptive. – joneshf May 08 '13 at 03:27
@Will Ness I got it working inclusively, but it doesn't work if M is initially 0 due to the base case. It doesn't get the element at index N. – Adam Duvall May 08 '13 at 03:48
@AdamDuvall it works as is now: `?- sublist(S,0,4,[0,1,2,3,4,5,6]). S = [0, 1, 2, 3] .` (the tweak is to use `M= – Will Ness May 08 '13 at 07:03
@WillNess I'm trying now to tweak it so that if `N > length(L)`, rather than evaluating to false, it acts as if `N = length(L)-1`. So, for example, `?- sublist(S,2,100,[0,1,2,3,4]). S = [2,3,4].` I got this working by adding a second predicate, sublist2 and changing the value of N, but I was curious if there's a simpler solution. – Adam Duvall May 08 '13 at 21:37
@AdamDuvall I don't think so, no. – Will Ness May 09 '13 at 05:31

CapelliC · Answer 2 · 2013-05-07T21:31:00.077

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).

Prolog: Create sublist, given two indices

2 Answers2

Linked