लिस्प

Question

मैं लिस्प में एक सूची उल्टा करने के लिए कोशिश कर रहा हूँ में सूची पीछे है, लेकिन मैं त्रुटि मिलती है: "त्रुटि: अपवाद C0000005 [झंडे 0] 20303FF3 पर {ऑफसेट 25 # अंदर} eax 108 EBX 200925CA ECX 200 EDX 2EFDD4D esp 2EFDCC8 ईबीपी 2EFDCE0 ईएसआई 628 ईडीआई 628 "

मेरे कोड इस प्रकार है:

(defun rev (l) 
    (cond 
     ((null l) '()) 
     (T (append (rev (cdr l)) (list (car l)))))) 

किसी को भी मुझे बता सकते हैं क्या मैं गलत कर रहा हूँ? अग्रिम में धन्यवाद!

Answer 1

आपका कोड लिखा के रूप में तार्किक रूप से सही है और नतीजा यह है कि आप इसे करना चाहते हैं पैदा करता है:

CL-USER> (defun rev (l) 
      (cond 
      ((null l) '()) 
      (T (append (rev (cdr l)) (list (car l)))))) 
REV 
CL-USER> (rev '(1 2 3 4)) 
(4 3 2 1) 
CL-USER> (rev '()) 
NIL 
CL-USER> (rev '(1 2)) 
(2 1) 

यानी, प्रदर्शन के मामले में यह के साथ कुछ मुद्दों कर रहे हैं। फ़ंक्शन संलग्न करें, लेकिन इसकी अंतिम तर्क के अलावा सभी की एक प्रति उत्पन्न करती है। उदा।, जब आप ('(1 2)' (ए बी) '(3 4)) संलग्न करते हैं, तो आप एक चार नई विपक्षी कोशिकाएं बना रहे हैं, जिनकी कारें 1, 2, ए, और बी हैं। अंतिम एक का सीडीआर मौजूदा सूची है (3 4)।

(defun append (l1 l2) 
    (if (null l1) 
     l2 
     (cons (first l1) 
      (append (rest l1) 
        l2)))) 

वास्तव में कॉमन लिस्प के संलग्न नहीं है यही कारण है, क्योंकि आम लिस्प के संलग्न ले जा सकते हैं और अधिक से अधिक दो तर्क: क्योंकि के कार्यान्वयन संलग्न कुछ इस तरह होता है। यह दिखाने के लिए काफी करीब है कि अंतिम सूची के अलावा सभी को कॉपी क्यों किया गया है। अब, हालांकि क्या कि के अपने कार्यान्वयन के संदर्भ में इसका मतलब है पर देखने के फिरना:

(defun rev (l) 
    (cond 
    ((null l) '()) 
    (T (append (rev (cdr l)) (list (car l)))))) 

इसका मतलब यह है कि जब आप (1 2 3 4)की तरह एक सूची पीछे रहे हैं, यह है कि आप कर रहे हैं :

(append '(4 3 2) '(1))    ; as a result of (1) 
(append (append '(4 3) '(2)) '(1)) ; and so on...  (2) 

अब, लाइन (2) में, आप सूची कॉपी कर रहे हैं (4 3)। एक पंक्ति में, आप सूची (4 3 2) की प्रतिलिपि बना रहे हैं जिसमें एक प्रति (4 3) शामिल है। यही है, आप प्रतिलिपि कॉपी कर रहे हैं। यह स्मृति का एक बहुत अपर्याप्त उपयोग है।

एक और आम दृष्टिकोण एक संचयक चर और एक सहायक समारोह का उपयोग करता है। (ध्यान दें कि मैं ENDP, बाकी, पहले, और सूची * बजाय अशक्त, सीडीआर की, कार, और विपक्ष का उपयोग करें, क्योंकि यह यह स्पष्ट है कि हम कर रहे हैं कि बनाता है , सूचियों के साथ काम नहीं कर मनमाने ढंग से विपक्ष के पेड़ों। वे बहुत ज्यादा एक ही कर रहे हैं (लेकिन कुछ मतभेद हैं)।)

(defun rev-helper (list reversed) 
    "A helper function for reversing a list. Returns a new list 
containing the elements of LIST in reverse order, followed by the 
elements in REVERSED. (So, when REVERSED is the empty list, returns 
exactly a reversed copy of LIST.)" 
    (if (endp list) 
     reversed 
     (rev-helper (rest list) 
        (list* (first list) 
         reversed)))) 

CL-USER> (rev-helper '(1 2 3) '(4 5)) 
(3 2 1 4 5) 
CL-USER> (rev-helper '(1 2 3) '()) 
(3 2 1) 

इस सहायक समारोह के साथ

, यह राजस्व परिभाषित करने के लिए आसान है:

(defun rev (list) 
    "Returns a new list containing the elements of LIST in reverse 
order." 
    (rev-helper list '())) 

CL-USER> (rev '(1 2 3)) 
(3 2 1) 

कहा यही कारण है, बल्कि एक बाहरी सहायक समारोह की तुलना में, यह शायद अधिक लेबल का उपयोग करने के लिए आम हो जाएगा एक स्थानीय सहायक समारोह को परिभाषित करने के:

(defun rev (list) 
    (labels ((rev-helper (list reversed) 
      #| ... |#)) 
    (rev-helper list '()))) 

या , के बाद से कॉमन लिस्प पूंछ कॉल अनुकूलन करने के लिए गारंटी नहीं है, एक कर पाश अच्छे और साफ यहाँ भी है:

(defun rev (list) 
    (do ((list list (rest list)) 
     (reversed '() (list* (first list) reversed))) 
     ((endp list) reversed))) 

Answer 2

एएनएसआई कॉमन लिस्प में, आप reverse समारोह का उपयोग करके सूची पलट सकता है (nondestructive: एक नई सूची आवंटित करती है), या nreverse (बिल्डिंग ब्लॉक या मौजूदा सूची की डेटा rearranges उलट एक निर्माण करने के लिए)।

> (reverse '(1 2 3)) 
(3 2 1) 

उद्धृत सूची अक्षर पर nreverse का उपयोग न करें; यह अपरिभाषित व्यवहार है और आश्चर्यजनक तरीकों से व्यवहार कर सकता है, क्योंकि यह de facto स्व-संशोधित कोड है।

Answer 3

यदि आप append जैसे मानक सीएल लाइब्रेरी फ़ंक्शंस का उपयोग कर सकते हैं, तो आपको reverse (Kaz suggested के रूप में) का उपयोग करना चाहिए।

अन्यथा, यदि यह एक व्यायाम (ज/डब्ल्यू या नहीं) है, तो आप इस कोशिश कर सकते हैं:

(defun rev (l) 
    (labels ((r (todo) 
      (if todo 
       (multiple-value-bind (res-head res-tail) (r (cdr todo)) 
        (if res-head 
         (setf (cdr res-tail) (list (car todo)) 
          res-tail (cdr res-tail)) 
         (setq res-head (list (car todo)) 
          res-tail res-head)) 
        (values res-head res-tail)) 
       (values nil nil)))) 
    (values (r l)))) 

पी एस। आपकी विशिष्ट त्रुटि समझ में नहीं आ रही है, कृपया अपने विक्रेता से संपर्क करें।

Answer 4

आप ढेर स्थान से बाहर होने की संभावना रन है; यह पूंछ की स्थिति के बाहर, एक रिकर्सिव फ़ंक्शन, rev पर कॉल करने का परिणाम है।

(defun reving (list result) 
    (cond ((consp list) (reving (cdr list) (cons (car list) result))) 
     ((null list) result) 
     (t (cons list result)))) 

आप rev समारोह तो हो जाता है::

(define rev (list) (reving list '())) 

उदाहरण:

* (reving '(1 2 3) '()) 
(3 2 1) 
* (reving '(1 2 . 3) '()) 
(3 2 1) 

* (reving '1 '()) 
(1)