Как удалить последний элемент из списка в Prolog?

Question

Я в следующей ситуации: у меня есть список, и я бы удалить из него только последний элемент.

У меня есть реализовать следующее правило (которые не работают хорошо):

deleteLastElement([Only],WithoutLast) :- 
    !, 
    delete([Only],Only,WithoutLast). 
deleteLastElement([_|Tail],WithoutLast) :- 
    !, 
    deleteLastElement(Tail,WithoutLast). 

Проблема заключается в том, что, когда я называю это все элемент в списке будут удалены, на самом деле, если я исполню следующее заявление я получаю:

[debug] ?- deleteLastElement([a,b,c], List). 
List = []. 

Глядя на след, я думаю, что это ясно, причина этой проблемы:

[trace] ?- deleteLastElement([a,b], List). 
    Call: (7) deleteLastElement([a, b], _G396) ? creep 
    Call: (8) deleteLastElement([b], _G396) ? creep 
    Call: (9) lists:delete([b], b, _G396) ? creep 
    Exit: (9) lists:delete([b], b, []) ? creep 
    Exit: (8) deleteLastElement([b], []) ? creep 
    Exit: (7) deleteLastElement([a, b], []) ? creep 
List = []. 

Когда базовый случай достигнут, список WithoutLast унифицирован с пустым списком [], а когда с возвратами выполняется WithoutLast по-прежнему остаются пустым списком.

Это не хорошо.

Я думал осуществить это делать следующие операции:

1. Подсчитать количество элементов в списке, прежде чем вызвать предикат, удалить последний элемент.
2. Iterate рекурсии и уменьшение значения числа элементов каждый раз, когда
3. Если это верно, что число элементов равно 0, это означает, что это последний элемент, поэтому я удалить его из исходного списка

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

Answer 1

Для предотвращения создания ненужных choicepoints, использовать отстающий воспользоваться первым аргументом индексирования:

list_butlast([X|Xs], Ys) :-     % use auxiliary predicate ... 
    list_butlast_prev(Xs, Ys, X).   % ... which lags behind by one item 

list_butlast_prev([], [], _). 
list_butlast_prev([X1|Xs], [X0|Ys], X0) :- 
    list_butlast_prev(Xs, Ys, X1).   % lag behind by one 

Примеров запросов:

?- list_butlast([], _). 
false. 

?- list_butlast([1], Xs). 
Xs = [].         % succeeds deterministically 

?- list_butlast([1,2], Xs). 
Xs = [1].         % succeeds deterministically 

?- list_butlast([1,2,3], Xs). 
Xs = [1,2].         % succeeds deterministically 

Как о другом направлении?

?- list_butlast(Xs, []). 
Xs = [_A]. 

?- list_butlast(Xs, [1,2,3]). 
Xs = [1,2,3,_A]. 

Как насчет наиболее общего запроса?

?- list_butlast(Xs, Ys). 
    Xs = [_A], Ys = [] 
; Xs = [_A,_B], Ys = [_A] 
; Xs = [_A,_B,_C], Ys = [_A,_B] 
; Xs = [_A,_B,_C,_D], Ys = [_A,_B,_C] 
; Xs = [_A,_B,_C,_D,_E], Ys = [_A,_B,_C,_D] 
... 

Answer 2

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

без использования разреза:

deleteLastElement([_], []). 
deleteLastElement([Head, Next|Tail], [Head|NTail]):- 
    deleteLastElement([Next|Tail], NTail). 

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

Второе предложение гласит, что, когда первым аргументом является список с по меньшей мере двумя элементами, то вы рекурсивно называете себя (без головы), добавляете Head во второй аргумент, возвращаемый этим вызовом.

На самом деле вам не нужно четко указать во втором пункте, что список должен иметь по крайней мере два элемента,

deleteLastElement([Head|Tail], [Head|NTail]):- 
    deleteLastElement(Tail, NTail). 

И, конечно же, вы можете также использовали append/3 для удаления последний элемент из списка:

append(WithoutLast, [_], List). 

Answer 3

Я нахожу ваш анализ немного сложным.Начнем с базового футляра:

without_last([_], []). 

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

Следовательно, индуктивный случай должен иметь место, когда мы не находимся в последнем элементе. В случае, когда у меня есть некоторый элемент, прикрепленный к произвольно длинному списку, этот список без последнего элемента - это только хвост списка без последнего элемента с текущим элементом спереди. Или:

without_last([X|Xs], [X|WithoutLast]) :- 
    without_last(Xs, WithoutLast). 

Это работает во всех направлениях.

?- without_last([1,2,3,4], X). 
X = [1, 2, 3] ; 
false. 

?- without_last([1,2], X). 
X = [1] . 

?- without_last([1], X). 
X = [] ; 
false. 

?- without_last([], X). 
false. 

?- without_last(X, [1,2,3]). 
X = [1, 2, 3, _G294]. 

?- without_last([1,2,3,4], [1,2,3]). 
true. 

?- without_last([1,2,3,X], [1,2,3]). 
true. 

Answer 4

@ реализация повторить является, безусловно, наиболее эффективным с современными процессорами Пролога, до сих пор я хотел бы использовать DCGs для этой цели - втайне надеясь, что один день технологии реализации будет достаточно, чтобы запустить это с сопоставимым (пробел) эффективность.

list_butlast(Xs, Ys) :- 
    phrase((seq(Ys), [_]), Xs). 

seq([]) --> 
    []. 
seq([E|Es]) --> 
    [E], 
    seq(Es).