common-lisp
विपक्ष कोशिकाओं और सूचियों

एक सम्मेलन के रूप में सूचीबद्ध करता है

कुछ भाषाओं में एक सूची डेटा संरचना शामिल है। आम लिस्प, और लिस्प परिवार की अन्य भाषाएँ, सूचियों का व्यापक उपयोग करती हैं (और लिस्प नाम एक LISt प्रोसेसर के विचार पर आधारित है)। हालांकि, आम लिस्प वास्तव में एक आदिम सूची डेटाटाइप को शामिल नहीं करता है। इसके बजाय, सूची सम्मेलन द्वारा मौजूद हैं। सम्मेलन दो सिद्धांतों पर निर्भर करता है:

1. प्रतीक शून्य खाली सूची है।
2. एक गैर खाली सूची एक आम सेल है जिसकी कार सूची का पहला तत्व है, और जिसका सीडीआर बाकी सूची है।

वह सब कुछ सूचियों के लिए है। यदि आपने उदाहरण को पढ़ा है, तो एक आम सेल क्या है? , तो आप जानते हैं कि एक आम सेल जिसकी कार X है और जिसका cdr Y है, को (X Y) लिखा जा सकता है। इसका मतलब है कि हम ऊपर के सिद्धांतों के आधार पर कुछ सूचियां लिख सकते हैं। तत्वों की सूची 1, 2, और 3 बस है:

(1 . (2 . (3 . nil)))

हालाँकि, क्योंकि सूचियाँ भाषाओं के लिस्प परिवार में इतनी सामान्य हैं, इसलिए सामान्य कोशिकाओं के लिए विशेष मुद्रण अभिसरण हैं जो कि सामान्य कोशिकाओं से जोड़े गए हैं।

1. प्रतीक नहीं के बराबर के रूप में भी लिखा जा सकता है ()।
2. जब एक कॉन्स सेल का cdr एक अन्य सूची (या तो ) या एक कॉन्स सेल है, तो एक कॉन सेल को डॉटेड जोड़ी नोटेशन के साथ लिखने के बजाय, "लिस्ट नोटेशन" का उपयोग किया जाता है।

सूची संकेतन को कई उदाहरणों द्वारा स्पष्ट रूप से दिखाया गया है:

(x . (y . z))   === (x y . z)
(x . NIL)       === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ())        === (1)

विचार यह है कि सूची के तत्व कोष्ठक के भीतर क्रमिक क्रम में लिखे गए हैं जब तक कि सूची में अंतिम सीडीआर नहीं पहुंच जाता है। यदि अंतिम सीडीआर शून्य (खाली सूची) है, तो अंतिम कोष्ठक लिखा जाता है। यदि अंतिम सीडीआर शून्य नहीं है (जिस स्थिति में सूची को अनुचित सूची कहा जाता है), तो एक बिंदु लिखा जाता है, और फिर अंतिम सीडीआर लिखा जाता है।

कॉन्स सेल क्या है?

एक आम कोशिका, जिसे एक बिंदीदार जोड़ी (इसके मुद्रित प्रतिनिधित्व के कारण) के रूप में भी जाना जाता है, बस दो वस्तुओं की एक जोड़ी है। एक कॉन सेल फंक्शन cons द्वारा बनाई गई है, और जोड़ी में तत्वों को car और cdr का उपयोग करके निकाला जाता है।

(cons "a" 4)

उदाहरण के लिए, यह एक जोड़ी देता है जिसका पहला तत्व (जिसे car साथ निकाला जा सकता है) "a" , और जिसका दूसरा तत्व (जिसे cdr साथ निकाला जा सकता है), 4 ।

(car (cons "a" 4))
;;=> "a"

(cdr (cons "a" 4))
;;=> 3

विपक्ष कोशिकाओं को डॉटेड युग्म संकेतन में मुद्रित किया जा सकता है:

(cons 1 2)
;;=> (1 . 2)

विपक्ष कोशिकाओं को बिंदीदार युग्म संकेतन में भी पढ़ा जा सकता है, ताकि

(car '(x . 5))
;;=> x

(cdr '(x . 5))
;;=> 5

(सामान्य कोशिकाओं का मुद्रित रूप थोड़ा अधिक जटिल हो सकता है, भी। इसके बारे में अधिक जानकारी के लिए, सूची के रूप में सामान्य कोशिकाओं के बारे में उदाहरण देखें।)

बस; व्यंजन कोशिकाएँ फंक्शन cons द्वारा बनाए गए तत्वों के जोड़े हैं, और तत्वों को car और cdr साथ निकाला जा सकता है। उनकी सादगी के कारण, कॉन्स सेल अधिक जटिल डेटा संरचनाओं के लिए एक उपयोगी बिल्डिंग ब्लॉक हो सकते हैं।

स्केचिंग कंस सेल्स

सहमति और सूचियों के शब्दार्थ को बेहतर ढंग से समझने के लिए, इस तरह की संरचनाओं का एक चित्रमय प्रतिनिधित्व अक्सर उपयोग किया जाता है। एक कॉन्स सेल आमतौर पर संपर्क में दो बॉक्स के साथ दर्शाया जाता है, जिसमें दो तीर होते हैं जो car और cdr मानों को इंगित करते हैं, या सीधे मान। उदाहरण के लिए, का परिणाम:

(cons 1 2)   
;; -> (1 . 2)

इनमें से किसी एक चित्र के साथ प्रतिनिधित्व किया जा सकता है:

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

इसलिए, उदाहरण के लिए:

(cons 1 (cons 2 (cons 3 4)))   ; improper “dotted” list
;; -> (1 2 3 . 4)

के रूप में प्रतिनिधित्व किया है:

जबकि:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))  ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)

के रूप में प्रतिनिधित्व किया है:

यहाँ एक पेड़ जैसी संरचना है:

(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4)         ; note the printing as an improper list

अंतिम उदाहरण से पता चलता है कि यह नोटेशन हमें भाषा के महत्वपूर्ण शब्दार्थ पहलुओं को समझने में कैसे मदद कर सकता है। सबसे पहले, हम पिछले एक के समान एक अभिव्यक्ति लिखते हैं:

(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)

इसे सामान्य तरीके से दर्शाया जा सकता है:

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

(let ((cell-a (cons 1 2)))
  (cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)

लेकिन, अगर हम आरेख आकर्षित, हम देख सकते हैं कि अभिव्यक्ति की अर्थ विज्ञान अलग है, के बाद से एक ही सेल के दोनों मूल्य है car हिस्सा है और cdr बाहरी का हिस्सा cons (यह है, cell-a साझा किया जाता है) :

और तथ्य यह है कि दो परिणामों के शब्दार्थ वास्तव में भाषा के स्तर पर भिन्न हैं, निम्नलिखित परीक्षणों द्वारा सत्यापित किए जा सकते हैं:

(let ((c1 (cons (cons 1 2) (cons 1 2)))
      (c2 (let ((cell-a (cons 1 2)))
            (cons cell-a cell-a))))
  (list (eq (car c1) (cdr c1))
        (eq (car c2) (cdr c2)))
;; -> (NIL T)

पहले eq झूठ है क्योंकि car और cdr के c1 संरचना की दृष्टि से बराबर (कि द्वारा सच है कर रहे हैं equal ), लेकिन "समान" (यानी "एक ही साझा संरचना") नहीं कर रहे हैं, जबकि दूसरे टेस्ट में परिणाम के बाद से सच है c2 की car और cdr समान हैं , यही है कि वे समान संरचना हैं ।