prolog - 在 Prolog 中将列表向左移动 N 次

Question

我正在尝试在 Prolog shiftL(L1,N,L2) 中建立一个关系，将 L1 向左移动 N 次(旋转)，结果为 L2，因此例如 shiftL([1,2,3], 2, [3,1,2]) 为 true。

我尝试了以下方法:

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

它工作得很好，但是在给我结果之后，它总是继续做其他事情，我得到了堆栈溢出:

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

我不知道是什么原因造成的。我认为我用第二行和 N=\=1 语句涵盖了基本情况。

预先感谢您的帮助!

Answer 1

这是相关的程序片段( failure-slice ):

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

我相信你可以自己解决这个问题。

有关故障切片如何缩小非终止问题范围的更多示例，请参阅 failure-slice .