Пролог -> У меня есть список [X, ..., Y, ... Z], как мне получить список, который идет только от X до Y?

Question

SWI-Пролог.
У меня есть список [X, ..., Y, ..., Z], как мне получить список, который идет только от X до Y?
То есть [ X, ..., Y , ..., Z] -> [X, ..., Y] .
Я почти ничего не знаю по этому языку, поэтому любая помощь приветствуется!
Я попробовал это:

bla([Ele|_], Ele, _). 
bla([H|T], Ele, Res):-
   append(Res, H, New_Res),
   bla([T], Ele, New_Res).  

Здесь Ele будет Y.
И я инициализировал то, что было бы Res как пустой список.

Повторяю, я новичок в этом языке, поэтому то, что я написал, может быть очень неправильным, извините!

Answer 1

В качестве альтернативы, поскольку ваш предикат описывает отношение между двумя списками и элементом сводки, вы можете использовать DCG для этой задачи:

list_pivot_sublist(L,P,S) :-
   phrase(sublist_till(L,P),S).  % the sublist up to the pivot element
                                 % is described by the DCG sublist_till//2

sublist_till([P|_],P) -->        % if the head of the list is P
   [P].                          % it's the last element in the sublist
sublist_till([X|Xs],P) -->       % if the head of the list is any element X
   [X],                          % X is in the sublist and
   sublist_till(Xs,P).           % the same goes for the tail and P

Теперь посмотрим на некоторые запросы:

Что такое подсписок [1,2,3,4,5] до элемента 3?

?- list_pivot_sublist([1,2,3,4,5],3,S).
S = [1, 2, 3] ;
false.

Какие пары sublist-pivot существуют для [1,2,3,4,5]?

?- list_pivot_sublist([1,2,3,4,5],P,S).
P = 1,
S = [1] ;
P = 2,
S = [1, 2] ;
P = 3,
S = [1, 2, 3] ;
P = 4,
S = [1, 2, 3, 4] ;
P = 5,
S = [1, 2, 3, 4, 5] ;
false.

Как может выглядеть исходный список и подходящий элемент поворота для подсписка [1,2,3]?

?- list_pivot_sublist(L,P,[1,2,3]).
L = [1, 2, 3|_G4751],
P = 3 ;
false.

Или самый общий запрос: Какие есть соответствующие списки, сводные элементы и подсписки?

?- list_pivot_sublist(L,P,S).
L = [P|_G4739],
S = [P] ;
L = [_G4738, P|_G4745],
S = [_G4738, P] ;
L = [_G4738, _G4744, P|_G4751],
S = [_G4738, _G4744, P] ;
L = [_G4738, _G4744, _G4750, P|_G4757],
S = [_G4738, _G4744, _G4750, P] ;
.
.
.

Это те же ответы, которые вы получаете с @ gusbro-версиями bla/3, за исключением этого запроса ...

?- bla(L,P,[1,2,3]).
L = [1, 2, 3|_G4739],
P = 3 ;

ERROR: Out of global stack

... который зацикливается на первой версии (с двумя append/3 в качестве целей) после предоставления единственного ответа. Причина этого в том, что первая цель дает бесконечное количество кандидатов на решение ...

?- append(NL1, [Ele|_], L).
NL1 = [],
L = [Ele|_G900] ;
NL1 = [_G1000],
L = [_G1000, Ele|_G900] ;
NL1 = [_G1000, _G1006],                                   % this candidate leads to
L = [_G1000, _G1006, Ele|_G900] ;                         % the only solution
NL1 = [_G1000, _G1006, _G1012],
L = [_G1000, _G1006, _G1012, Ele|_G900] ;
.
.
.

... все из них терпят неудачу, кроме помеченного в запросе выше:

?- append(NL1, [Ele|_], L), append(NL1, [Ele], [1,2,3]).
NL1 = [1, 2],                                             % corresponding answer
Ele = 3,                                                  % to the third candidate
L = [1, 2, 3|_G4641] ;                                    % above
ERROR: Out of global stack

Следовательно, версия без append/3 явно предпочтительнее. Со ссылкой на комментарий @lurker, я также хотел бы отметить, что с этими версиями вы получите несколько ответов, если элемент pivot встречается в списке более одного раза:

?- list_pivot_sublist([1,2,3,4,5,3],3,S).
S = [1, 2, 3] ;
S = [1, 2, 3, 4, 5, 3] ;

Если вы хотите получить только первый подсписок, вы можете изменить DCG-версию, добавив ограничение X, отличающееся от P, которое препятствует дальнейшим рекурсиям Prolog после первого успеха:

sublist_till([P|_],P) -->
   [P].
sublist_till([X|Xs],P) -->
   {dif(X,P)},                % <- new constraint
   [X],
   sublist_till(Xs,P).

Теперь приведенный выше запрос дает только один ответ:

?- list_pivot_sublist([1,2,3,4,5,3],3,S).
S = [1, 2, 3] ;
false.

Самый общий запрос также немного отличается, поскольку теперь он распространяет ограничения dif/2 вплоть до ответа:

?- list_pivot_sublist(L,P,S).
L = [P|_G4739],
S = [P] ;
L = [_G4886, P|_G4890],
S = [_G4886, P],
dif(_G4886, P) ;
L = [_G4942, _G4945, P|_G4949],
S = [_G4942, _G4945, P],
dif(_G4942, P),
dif(_G4945, P) ;
.
.
.

Вы можете изменить вторую версию @ gusbro таким же образом, добавив такое же ограничение к рекурсивному правилу:

bla([Ele|_], Ele, [Ele]).
bla([E|L], Ele, [E|NL]):-
  dif(E,Ele),                  % <- new constraint
  bla(L, Ele, NL).

Answer 2

Разве append/3 не дает уже того, что вы хотите?

?- append(L, [y|_], [x,x,x,y,x,y,x,z]).
L = [x, x, x] ;
L = [x, x, x, y, x] ;
false.

Вы можете повторно добавить последний элемент 'y' с помощью другого вызова append/3:

?- append(L, [y|_], [x,x,x,y,x,y,x,z]), append(L, [y], L1).
L1 = [x, x, x, y] ;
L1 = [x, x, x, y, x, y] ;
false.

Answer 3

Используя append/3 это может быть просто:

bla(L, Ele, NL):-
  append(NL1, [Ele|_], L),
  append(NL1, [Ele], NL).

Отметив, что append(L1,L2,L3) завершается успешно, когда L3 является объединением L1 и L2, вы можете извлечь элементы из L до нужного элемента с первым добавлением (append(NL1, [Ele|_], L)), где в этом примере L2 - это список, который начинается с элементом Ele, поэтому L - это список, который начинается с NL1 и для которого следующим элементом L является Ele.

Второе добавление используется для добавления Ele в конец NL1.

Без использования append/3 вы можете написать:

bla([Ele|_], Ele, [Ele]).
bla([E|L], Ele, [E|NL]):-
  bla(L, Ele, NL).

Обе реализации могут завершиться успешно более одного раза, если Ele появится более одного раза в L, и потерпит неудачу, если Ele не появится в L.