CODEWITHSUNDEEP
prologfailure-slice
BananaPants
BananaPants

Reputation: 25

Shifting a list to the left N times in Prolog

I'm trying to make a relation in Prolog shiftL(L1,N,L2) that shifts L1 to the left N times (rotationally), and the result is L2, so for example shiftL([1,2,3], 2, [3,1,2]) is true.

I tried the following:

shiftL([],N,[]).
shiftL([X|Xs],1,L) :- append(Xs,[X],L).
shiftL([X|Xs],N,L) :- N1 is N-1 , N=\=1 , shiftL(L1,N1,L) , append(Xs,[X],L1).

And it works great, but after giving me the result it always keeps doing something else and I get a stack overflow:

?- shiftL([1,2,3], 2, L).
L = [3, 1, 2] ;
ERROR: Out of global stack

And I have no idea what's causing that. I thought I covered the base case with the second line, and with the N=\=1 statement.

Thanks in advance for any help!

Upvotes: 2

Views: 888

Answers (1)

false
false

Reputation: 10122

Here is the relevant program fragment ():

shiftL([],N,[]) :- false.
shiftL([X|Xs],1,L) :-
   append(Xs,[X],L), false.
shiftL([X|Xs],N,L) :-
   N1 is N-1 ,
   N=\=1,
   shiftL(L1,N1,L), false,
   append(Xs,[X],L1).

So essentially the goal append(Xs,[X],L) loops. And it loops because neither Xs nor L is a list - that is a list with fixed length. To see this, consider the recursive goal shiftL(L1,N1,L). As you can see in the fragment, L1 occurs nowhere else. It is thus an uninstantiated variable. And L is the variable from the query. So you need to make either L1 or L a list. Like by putting the hidden append(Xs,[X],L1) in front.

There is another loop with:

?- shiftL([1,2,3],-1,L).

I believe you can solve that problem yourself.

For more examples how failure-slices can narrow down problems of non-termination, see .

Upvotes: 2

Related Questions