एक पूंछ-रिकर्सन संस्करण सूची संलग्न करने वाला फ़ंक्शन

Question

मुझे append को एक सूची में तत्व लागू करने के कई उदाहरण दिखाई देते हैं, लेकिन सभी पूंछ रिकर्सन का उपयोग नहीं कर रहे हैं। कार्यात्मक शैली में ऐसे फ़ंक्शन को कैसे कार्यान्वित करें?

(define (append-list lst elem) expr) 

Answer 1

खैर यह संभव एक पूंछ पुनरावर्ती append-element प्रक्रिया लिखने के लिए है ...

(define (append-element lst ele) 
    (let loop ((lst (reverse lst)) 
      (acc (list ele))) 
    (if (null? lst) 
     acc 
     (loop (cdr lst) (cons (car lst) acc))))) 

... लेकिन यह है कि reverse (अच्छा उपाय) में फेंक दिया के साथ और अधिक अक्षम है। मैं किसी अन्य कार्यात्मक (उदा।, इनपुट सूची को संशोधित किए बिना) इस प्रक्रिया को पहले सूची को वापस किए बिना पूंछ-रिकर्सन के रूप में लिखने का तरीका नहीं सोच सकता।

गैर-कार्यात्मक प्रश्न के उत्तर के लिए, @WillNess ने एक आंतरिक सूची उत्परिवर्तित एक अच्छा योजना समाधान प्रदान किया।

Answer 2

यह लिस्प, नहीं योजना है, लेकिन मुझे यकीन है कि आप अनुवाद कर सकते हैं हूँ:

(defun append-tail-recursive (list tail) 
    (labels ((atr (rest ret last) 
      (if rest 
       (atr (cdr rest) ret 
         (setf (cdr last) (list (car rest)))) 
       (progn 
        (setf (cdr last) tail) 
        ret)))) 
    (if list 
     (let ((new (list (car list)))) 
      (atr (cdr list) new new)) 
     tail))) 

मैं सिर रख और वापसी सूची की पूंछ और के रूप में मैं सूची तर्क पार पूंछ को संशोधित।

Answer 3

निम्नलिखित tail recursion modulo cons अनुकूलन का कार्यान्वयन है, जिसके परिणामस्वरूप पूरी तरह से पूंछ रिकर्सिव कोड है। यह इनपुट संरचना की प्रतिलिपि बनाता है और फिर ऊपर-नीचे तरीके से उत्परिवर्तन द्वारा, नया तत्व जोड़ता है। (यह में पारित किसी भी डेटा को बदल नहीं करता है और उसके परिणाम के उत्पादन के लिए छोड़कर कोई नमूदार असर पड़ता है) के बाद से इस उत्परिवर्तन अपने आंतरिक ताजा बनाए गए डेटा को किया जाता है, यह अभी भी बाहर की दुनिया में कार्यात्मक है:

(define (add-elt lst elt) 
    (let ((result (list 1))) 
    (let loop ((p result) (lst lst)) 
     (cond 
     ((null? lst) 
      (set-cdr! p (list elt)) 
      (cdr result)) 
     (else 
      (set-cdr! p (list (car lst))) 
      (loop (cdr p) (cdr lst))))))) 

मुझे पसंद है "हेड-सेंटीनेल" चाल का उपयोग करके, यह केवल एक अतिरिक्त विपक्ष सेल आवंटित करने की लागत पर कोड को बहुत सरल बनाता है।

यह कोड कुछ भाषाओं में (उदाहरण के लिए प्रोलॉग) को एक कंपाइलर द्वारा स्वचालित रूप से पूरा करने के लिए निम्न-स्तरीय उत्परिवर्तन प्राइमेटिव का उपयोग करता है। काल्पनिक योजना TRMC-के अनुकूलन में, हमने निम्न पूंछ पुनरावर्ती सापेक्ष विपक्ष कोड लिखने में सक्षम होगा, और एक संकलक स्वचालित रूप से है यह ऊपर कोड के कुछ बराबर में अनुवाद: अगर के लिए नहीं

(define (append-elt lst elt)    ;; %% in Prolog: 
    (if (null lst)       ;; app([], X, Z) :- Z=[X]. 
    (list elt)       ;; app([A|B], X, Z) :- 
    (cons (car lst)      ;; Z=[A|Y],   % cons _before_ 
      (append-elt (cdr lst) elt)))) ;; app(B, X, Y). % tail call 

cons ऑपरेशन, append-elt पूंछ-रिकर्सिव हो। यह वह जगह है जहां टीआरएमसी अनुकूलन खेल में आता है।

Answer 4

आप मूर्खतापूर्ण नहीं हो सकते हैं, लेकिन टीसीएमसी - टेल कॉल मॉड्यूलो कंस प्रदान करने वाले कार्यान्वयन भी देखें। यही कारण है कि

(cons head TAIL-EXPR) 

पूंछ-कॉल TAIL-EXPR करने के लिए

की अनुमति देता है, तो विपक्ष अपने आप में एक पूंछ-कॉल है।

Answer 5

यह एक कार्यात्मक, पूंछ पुनरावर्ती संलग्न-elt निरंतरता का उपयोग कर रहा है:

(define (cont-append-elt lst elt) 
    (let cont-loop ((lst lst) 
        (cont values)) 
    (if (null? lst) 
     (cont (cons elt '())) 
     (cont-loop (cdr lst) 
        (lambda (x) (cont (cons (car lst) x))))))) 

अभिनय की दृष्टि से यह विल के रैकेट और गैम्बिट में एक परिवर्तनशील है, लेकिन Ikarus में करीब है और चिकन ऑस्कर रिवर्स बेहतर किया। उत्परिवर्तन हमेशा सर्वश्रेष्ठ प्रदर्शन करने वाला था। हालांकि, मैंने इसका इस्तेमाल नहीं किया होगा, लेकिन ऑस्कर की प्रविष्टि का एक मामूली संस्करण, पूरी तरह से क्योंकि इसे पढ़ना आसान है।

(define (reverse-append-elt lst elt) 
    (reverse (cons elt (reverse lst)))) 

और तुम प्रदर्शन मैंने किया होता तो परिवर्तनशील चाहते हैं: है कि

(define (reverse!-append-elt lst elt) 
    (let ((lst (cons elt (reverse lst)))) 
    (reverse! lst) 
    lst))