Создать обведенный список в прологе

Question

Я пытаюсь создать эту функцию в Прологе:

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

это хорошо, но я хочу, чтобы это прекратилось после первого раза, когда я делаю все возможности.

Что я могу сделать?

Answer 1

Вы можете просто сформулировать проблему по-другому:

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

Так что это, по сути, ваша программа с одним дополнительным аргументом, используемым для ограничения количества рекурсий. Ограничение рекурсии таким способом обычно используется для реализации так называемых итеративных алгоритмов углубления. В этом случае, однако, у нас была одна граница глубины. Никакой дополнительной итерации не было необходимости.

Answer 2

Вам нужен еще один аргумент для вашего предиката. Одним из вариантов является использование элементов в вашем списке, пока вы не останетесь с [],

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

Answer 3

Вот более простое решение с гораздо более слабыми свойствами завершения. С другой стороны, вы заявили, что первый аргумент "полностью создан". Можете ли вы быстро создать тест для аргумента, который будет "полностью создан"? Я предполагаю, что нет. И именно по этой причине такие предположения приводят к такому количеству ошибок. Сначала программисты просто предполагают, что аргумент будет "полностью создан", а позже они забывают, что они предполагали...

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

Эта версия больше не заканчивается для circleList3(Xs, []), Чтобы понять, почему это так, я буду использовать срез-срез, то есть добавлю false в программе. Если оставшаяся часть все еще не заканчивается, то одна проблема заключается в видимой части.

? - circleList3 (Xs, []), false.
/ * LOOPS * /

circleList3 (Xs, Ys): -
   добавить (как, Bs, Xs), ложь,
   добавить (Bs, As, Ys),
   (As = []; As = [_ | _], Bs = [_ | _]).

Этот фрагмент ошибки не заканчивается, потому что первая цель вызывается с 3 необоснованными аргументами. Единственная помощь, чтобы получить это прекращение будет Ys Но никто не заинтересован в этом!

Теперь мы могли бы обменяться двумя целями append/3 заставить этот фрагмент завершиться, но тогда другие запросы не будут прекращены...