Làm thế nào để xóa phần tử cuối cùng khỏi danh sách trong Prolog?

Question

Tôi đang trong tình huống sau: Tôi có một danh sách và tôi sẽ chỉ xóa nó khỏi phần tử cuối cùng.

Tôi có thực hiện các nguyên tắc sau (mà không làm việc tốt):

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

Vấn đề là khi tôi gọi nó, tất cả các phần tử trong danh sách được xóa, trên thực tế nếu tôi thực hiện sau tuyên bố tôi có được:

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

Nhìn vào dấu vết tôi nghĩ rằng đó là rõ ràng nguyên nhân của vấn đề này:

[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 = []. 

Khi trường hợp cơ sở được đạt tới, danh sách WithoutLast được thống nhất với danh sách trống [] và khi quay lui được thực hiện các WithoutLast vẫn giữ nguyên danh sách trống.

Điều này không tốt.

Tôi đã suy nghĩ để thực hiện nó làm các hoạt động sau:

1. Đếm số phần tử trong danh sách trước khi gọi các vị đó xóa các yếu tố cuối cùng.
2. Lặp bằng đệ quy và giảm các giá trị của các số nguyên tố mỗi lần
3. Nếu đó là sự thật rằng số lượng phần tử là 0 có nghĩa rằng đây là yếu tố cuối cùng vì vậy tôi xóa nó khỏi danh sách ban đầu

Nhưng điều này dường như với tôi không rõ ràng và không tốt như vậy, tôi sẽ biết nếu có một giải pháp tốt tuyên bố cho vấn đề này.

Answer 1

Để ngăn chặn việc tạo ra các choicepoints vô dụng, sử dụng tụt được hưởng lợi từ đầu lập chỉ mục lập luận: Truy vấn

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 

mẫu:

?- 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 

Làm thế nào về một hướng khác?

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

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

Còn truy vấn chung nhất thì sao?

?- 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

Nếu bạn phát triển quy trình đệ quy, đi qua mọi phần tử của danh sách đầu vào, trường hợp cơ sở của bạn sẽ dừng khi bạn tìm phần tử cuối cùng hợp nhất danh sách kết quả với danh sách trống. Sau đó, trở về từ các đệ quy gọi bạn chỉ cần thêm tất cả các mục khác vào danh sách kết quả:

Nếu không sử dụng cắt:

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

Các khoản đầu tiên (trường hợp cơ sở) thống nhất đối số thứ hai với danh sách trống khi chỉ có một phần tử trong danh sách đối số đầu tiên. Điều khoản thứ hai nói rằng khi đối số đầu tiên là một danh sách có ít nhất hai phần tử, sau đó bạn đệ quy gọi chính nó (không có phần đầu), thêm đầu vào đối số thứ hai được trả về bởi cuộc gọi đó.

Trong thực tế, bạn không cần phải thực hiện rõ ràng trong mệnh đề thứ hai mà danh sách cần phải có ít nhất hai yếu tố,

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

Và, tất nhiên, bạn cũng có thể đã sử dụng để loại bỏ các append/3 mặt hàng cuối cùng từ danh sách:

append(WithoutLast, [_], List). 

Answer 3

Tôi thấy phân tích của bạn hơi quá phức tạp.Hãy bắt đầu từ trường hợp cơ sở:

without_last([_], []). 

Khi bạn ở phần tử cuối cùng, kết quả phải là danh sách trống.

Trường hợp quy nạp phải là trường hợp chúng tôi không ở phần tử cuối cùng. Trong trường hợp tôi có một số phần tử được gắn vào một danh sách dài tùy ý, danh sách đó không có phần tử cuối cùng chỉ là đuôi của danh sách mà không có phần tử cuối cùng với phần tử hiện tại ở phía trước. Hoặc:

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

Điều này hoạt động theo mọi hướng.

?- 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

@ thực hiện lặp lại chắc chắn là một trong những hiệu quả nhất với bộ vi xử lý Prolog hiện tại, tôi vẫn thích sử dụng DCG cho mục đích này - âm thầm hy vọng rằng công nghệ thực hiện một ngày nào đó sẽ là tốt, đủ để chạy này với so sánh (không gian) hiệu quả.

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

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