प्रोलॉग में एक सूची से अंतिम तत्व को कैसे हटाएं?

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. प्रत्यावर्तन द्वारा दोहराएं और तत्व की संख्या का मूल्य हर बार
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). 

पहले खंड (आधार मामले) खाली सूची जब साथ दूसरा तर्क सम्मिलित है:

कटौती का उपयोग कर के बिना पहली तर्क सूची में केवल एक तत्व है।

दूसरा खंड कहता है कि जब पहला तर्क कम से कम दो तत्वों के साथ एक सूची है, तो आप फिर से कॉल (सिर के बिना) को कॉल करते हैं, उस कॉल द्वारा लौटाए गए दूसरे तर्क में हेड जोड़ें।

वास्तव में आप दूसरा खंड है कि सूची में कम से कम दो तत्वों की जरूरत है में स्पष्ट बनाने के लिए की जरूरत नहीं है,

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

@ दोहराने के कार्यान्वयन निश्चित रूप से वर्तमान Prolog प्रोसेसर के साथ सबसे कुशल एक है, फिर भी मैं इस उद्देश्य के लिए DCGs का उपयोग करना चाहते - चुपके से उम्मीद है कि एक दिन कार्यान्वयन प्रौद्योगिकी काफी अच्छा तुलनीय (स्थान) के साथ इस चलाने के लिए किया जाएगा दक्षता।

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

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