slicing a list into a smaller list

Question

I'm currently working through the 99 Prolog problems list http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ and am on question 18. It states:

Given two indices, I and K, the slice is the list containing the elements between the I'th and K'th element of the original list (both limits included). Start counting the elements with 1.

Example query: ?- slice([a,b,c,d,e,f,g,h,i,k],3,7,L).
Expected result: L = [c,d,e,f,g]

I've looked at the given solution, but my question was whether anyone could figure out why my solution was wrong? This is my code:

chop([H|_],_,End,End,[H]).
chop([_|L],Start,End,Count,Out) :-
    (Count < Start),
    N is Count + 1,
    chop(L,Start,End,N,Out).
chop([H|L],Start,End,Count,[H|Out]) :-
    (Count >= Start; Count < End),
    N is Count + 1,
    chop(L,Start,End,N,Out).

slice(L,Start,End,Out) :-
    (Start =< End),
    Count is 1,
    chop(L,Start,End,Count,Out).

My train of thought was: if the element at iteration 'Count' is between the two given limits then add to the list, if not then move on. As an example output, for the call:

?- slice([a,b,c,d,e],2,3,X).

I get the output:

X = [b,c] ? ;
X = [b,c] ? ;
X = [a,b,c] ? ;
X = [a,b,c] ? ;

And for the call:

?- slice([a,b,c,d,e],3,3,X).
X = [c] ? ;
X = [b,c] ? ;
X = [a,c] ? ;
X = [a,b,c] ? ;

The first given list is correct but then it all goes wrong; I've tried using trace but it's boggling my mind.

Answer 1

We define slice/4 based on append/3 and length/2, as defined by the Prolog Prologue:

slice(AsBsCs,P,Q,Bs) :-
   append(AsBs,_Cs,AsBsCs),
   append(As  , Bs,AsBs  ),
   length([_|As],P),
   length( AsBs ,Q).

Sample query as given by the OP:

?- slice([a,b,c,d,e,f,g,h,i,k],3,7,Xs).
Xs = [c,d,e,f,g] ;
false.

Let's generalize above query like this:

?- slice([a,b,c,d,e,f,g,h,i,k],P,7,Xs).
  P = 1, Xs = [a,b,c,d,e,f,g]
; P = 2, Xs =   [b,c,d,e,f,g]
; P = 3, Xs =     [c,d,e,f,g]
; P = 4, Xs =       [d,e,f,g]
; P = 5, Xs =         [e,f,g]
; P = 6, Xs =           [f,g]
; P = 7, Xs =             [g]
; P = 8, Xs =              [] 
; false.

How about generalizing a different way?

?- slice([a,b,c,d,e,f,g,h,i,k],3,Q,Xs).
; Q =  2, Xs = []
; Q =  3, Xs = [c]
; Q =  4, Xs = [c,d]
; Q =  5, Xs = [c,d,e]
; Q =  6, Xs = [c,d,e,f]
; Q =  7, Xs = [c,d,e,f,g]
; Q =  8, Xs = [c,d,e,f,g,h]
; Q =  9, Xs = [c,d,e,f,g,h,i]
; Q = 10, Xs = [c,d,e,f,g,h,i,k]
; false.

Last, we run a query which is a generalization of both:

?- slice([a,b,c,d,e,f,g,h,i,k],P,Q,Xs).
  P =  1, Q =  0, Xs = []
; P =  1, Q =  1, Xs = [a]
; P =  2, Q =  1, Xs = []
; P =  1, Q =  2, Xs = [a,b]
; P =  2, Q =  2, Xs = [b]
; P =  3, Q =  2, Xs = []
; P =  1, Q =  3, Xs = [a,b,c]
; P =  2, Q =  3, Xs = [b,c]
; P =  3, Q =  3, Xs = [c]
; P =  4, Q =  3, Xs = []
; P =  1, Q =  4, Xs = [a,b,c,d]
; P =  2, Q =  4, Xs = [b,c,d]
; P =  3, Q =  4, Xs = [c,d]
; P =  4, Q =  4, Xs = [d]
; P =  5, Q =  4, Xs = []
; P =  1, Q =  5, Xs = [a,b,c,d,e]
; P =  2, Q =  5, Xs = [b,c,d,e]
; P =  3, Q =  5, Xs = [c,d,e]
; P =  4, Q =  5, Xs = [d,e]
; P =  5, Q =  5, Xs = [e]
; P =  6, Q =  5, Xs = []
; P =  1, Q =  6, Xs = [a,b,c,d,e,f]
; P =  2, Q =  6, Xs = [b,c,d,e,f]
; P =  3, Q =  6, Xs = [c,d,e,f]
; P =  4, Q =  6, Xs = [d,e,f]
; P =  5, Q =  6, Xs = [e,f]
; P =  6, Q =  6, Xs = [f]
; P =  7, Q =  6, Xs = []
; P =  1, Q =  7, Xs = [a,b,c,d,e,f,g]
; P =  2, Q =  7, Xs = [b,c,d,e,f,g]
; P =  3, Q =  7, Xs = [c,d,e,f,g]
; P =  4, Q =  7, Xs = [d,e,f,g]
; P =  5, Q =  7, Xs = [e,f,g]
; P =  6, Q =  7, Xs = [f,g]
; P =  7, Q =  7, Xs = [g]
; P =  8, Q =  7, Xs = []
; P =  1, Q =  8, Xs = [a,b,c,d,e,f,g,h]
; P =  2, Q =  8, Xs = [b,c,d,e,f,g,h]
; P =  3, Q =  8, Xs = [c,d,e,f,g,h]
; P =  4, Q =  8, Xs = [d,e,f,g,h]
; P =  5, Q =  8, Xs = [e,f,g,h]
; P =  6, Q =  8, Xs = [f,g,h]
; P =  7, Q =  8, Xs = [g,h]
; P =  8, Q =  8, Xs = [h]
; P =  9, Q =  8, Xs = []
; P =  1, Q =  9, Xs = [a,b,c,d,e,f,g,h,i]
; P =  2, Q =  9, Xs = [b,c,d,e,f,g,h,i]
; P =  3, Q =  9, Xs = [c,d,e,f,g,h,i]
; P =  4, Q =  9, Xs = [d,e,f,g,h,i]
; P =  5, Q =  9, Xs = [e,f,g,h,i]
; P =  6, Q =  9, Xs = [f,g,h,i]
; P =  7, Q =  9, Xs = [g,h,i]
; P =  8, Q =  9, Xs = [h,i]
; P =  9, Q =  9, Xs = [i]
; P = 10, Q =  9, Xs = []
; P =  1, Q = 10, Xs = [a,b,c,d,e,f,g,h,i,k]
; P =  2, Q = 10, Xs = [b,c,d,e,f,g,h,i,k]
; P =  3, Q = 10, Xs = [c,d,e,f,g,h,i,k]
; P =  4, Q = 10, Xs = [d,e,f,g,h,i,k]
; P =  5, Q = 10, Xs = [e,f,g,h,i,k]
; P =  6, Q = 10, Xs = [f,g,h,i,k]
; P =  7, Q = 10, Xs = [g,h,i,k]
; P =  8, Q = 10, Xs = [h,i,k]
; P =  9, Q = 10, Xs = [i,k]
; P = 10, Q = 10, Xs = [k]
; P = 11, Q = 10, Xs = []
; false.

Answer 2

the problem you have is that your rules are not mutually exclusive everything that matches with your second rule

chop([_|L],Start,End,Count,Out) :-

will also match with your third rule

chop([H|L],Start,End,Count,[H|Out]) :-

Meaning that once you have found a working answer, and try to find more, every successful branching into the second rule will result in a second answer following the third branch. (hence the additional prepended letter)

you could solve this by adding a cut in at the end of the second rule

chop([_|L],Start,End,Count,Out) :-
  (Count < Start),
  N is Count + 1,
  chop(L,Start,End,N,Out),
  !.