Обрезать максимальный префикс, состоящий из одинаковых элементов

Question

Мне трудно придумать эффективный пункт, заданный для следующей задачи: по списку X найти его максимальный префикс, состоящий из тех же элементов, вместе с оставшимся суффиксом. То есть:

| ?- trim([a,a,a,b,b,c], [a,a,a], [b,b,c]).
yes

| ?- trim([a,a,a,a,b,b,c,c], X, Y).
X = [a,a,a,a],
Y = [b,b,c,c]

Вот что у меня есть:

same([]).
same([_]).
same([X,X|T]) :- same([X|T]).

trim([], [], []).
trim(L, L, []) :- same(L).
trim(L, [A|B], [C|D]) :- append([A|B], [C|D], L), A \= C, same([A|B]).

Партия append кажется не очень эффективной. Есть ли простой итеративный способ сделать это?

Answer 1

Думая об этой проблеме с самого начала, мы знаем, что хотим, чтобы тривиальный случай был истинным:

trim([], [], []).

Тогда нам нужен самый длинный регистр префикса элемента:

trim([X], [X], []).           % Trivial case
trim([X,Y|T], [X], [Y|T]) :-  % Non-repeating element, ends recursion
    dif(X, Y).
trim([X,X|T], [X|Xs], S) :-   % Repeating element, recursive case
    trim([X|T], Xs, S).