在Prolog中创建圆形列表

Question

我正在尝试在Prolog中创建这个函数：

% Signature: circleList(L1, L2)/2
% Purpose: L2 is a "circled" L1 list.
% Precondition: L1 is fully instantiated.
% Examples:
% ?- circleList([2, 3, 4, 5], X).
% X = [2, 3, 4, 5];
% X = [3, 4, 5, 2];
% X = [4, 5, 2, 3];
% X = [5, 2, 3, 4];
% false.

所以我做了这个：

circleList([],[]).
circleList(X,X).
circleList([H|T],R):- append(T,[H],S), circleList(S,R).

但输出结果是这样的：

X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] 
and so on...

这很好，但我希望它在第一次后停止，我正在尝试所有可能性。

我该怎么办？

- kitsuneFox

Answer 1

你的谓词需要另一个参数。一种方法是消耗列表中的元素，直到你剩下 []。

circleList([Head|Tail],CL):-
    circleList(Tail,[Head],CL).

circleList([],L,L).
circleList([Head|Tail], Rest, CL):-
    append(Rest, [Head], NewRest),
    circleList(Tail, NewRest, CL).
circleList([Head|Tail], Rest, CL):-
    append([Head|Tail], Rest,CL).

我看到的另一个选择是使用length/2将深度限制为列表的大小。

circleList([],[]).
circleList(List,CL):-
    length(List, N),
    circleList(List,N,CL).

circleList(_,0,_):-!, fail.
circleList(List,_,List).
circleList([Head|Tail], N, CL):-
    append(Tail, [Head], NewList),
    N1 is N - 1,
    circleList(NewList, N1, CL).

- Tudor Berariu

Answer 2

您可以简单地用不同的方式表述问题：

rotatelist([], []).
rotatelist(Xs, Ys) :-
   Xs = [_|_],
   Ys = [_|_],
   same_length(Xs, Ys), % avoid non-termination
   Bs = [_|_],          % avoid redundant answers
   append(As,Bs,Xs),
   append(Bs,As,Ys).

same_length([], []).
same_length([_E|Es], [_F|Fs]) :-
   same_length(Es, Fs).

但是，如果你的意图是明确停止；那么这很容易出现错误。实际上，我没有看到如何自然地使用截断的方法。

不过，你可以通过以下方式限制递归次数：

circleList2(Xs, Ys) :-
   same_length(Xs, Ys),
   circleList2(Xs, Ys, Xs).

circleList2(X,X, _).
circleList2([H|T],R, [_|L]):-
   L = [_|_],
   append(T,[H],S),
   circleList2(S,R, L).

因此，这基本上是您的程序，其中使用了一个额外的参数来限制递归次数。以这种方式限制递归通常用于实现所谓的迭代加深算法。然而，在这种情况下，我们只有一个深度限制。不需要额外的迭代。

- false

---

我不能限制它，也无法创建一个包含3个变量的谓词，除非它像是一个“辅助函数”。这是我在使用Prolog进行关系逻辑编程基础作业中遇到的问题，所以我需要更好的解释。 - kitsuneFox

@kitsuneFox：为什么你不能限制它？same_length/2和circleList2/3是辅助谓词。 - false

@TudorBerariu：因为循环circleList(L，[1,2])会产生冗余解决方案，例如circleList([1,2]，L)。 - false

目标append(A, B, L).具有两个未绑定变量A，B，对于所有连接起来得到结果L的列表A，B都满足。(例如：?- append(A,B,[a,b,c]). A = [], B = [a, b, c] ; A = [a], B = [b, c] ; A = [a, b], B = [c] ; A = [a, b, c], B = [] ; false.) - Tudor Berariu

https://dev59.com/9l3Ua4cB1Zd3GeqP-Cw8，https://dev59.com/pnnZa4cB1Zd3GeqPoErj - Fred Foo

Answer 3

这里提供了一种更简单的解决方案，但其终止特性较弱。另一方面，你指出第一个参数是“完全实例化的”。你能否迅速为判断参数是否“完全实例化”提供一个测试用例？我猜想不行。正是因为这个原因，这样的假设会导致很多错误。首先，程序员只是假定参数将被“完全实例化”，后来他们忘记了自己的假设...

circleList3(Xs, Ys) :-
   append(As, Bs, Xs),
   append(Bs, As, Ys),
   ( As = [] ; As = [_|_], Bs = [_|_] ).

这个版本现在不再对circleList3（Xs，[]）终止。为了看到原因，我将使用一个failure-slice，也就是说，我会在程序中添加false。如果剩余部分仍然无法终止，则问题在可见部分。

?- circleList3(Xs, []), false.
   循环。
circleList3(Xs，Ys)：
   追加（As，Bs，Xs），假，
   append（Bs，As，Ys），
   （As = []; As = [_ | _]，Bs = [_ | _]）。

这个失败切片没有终止，因为第一个目标被调用时有3个未实例化的参数。唯一能帮助它终止的是Ys，但没有人对它感兴趣！

我们现在可以交换两个目标append/3使这个片段终止，但是，其他查询将不会终止...

- false