लंबोदर कार्यों की सूची

अनुवादक का नोट: यहां मूल। मूल के सभी उदाहरण जावास्क्रिप्ट में लिखे गए हैं, लेकिन मैंने उन्हें योजना में अनुवाद करने का निर्णय लिया। मुझे यकीन है कि यह कम स्पष्ट नहीं हुआ है, लेकिन इस भाषा की सभी सुंदरता दिखाई देती है।
UPD: जावास्क्रिप्ट में मूल उदाहरण को दाईं ओर के सभी उदाहरणों में जोड़ा गया।


यदि आप कंप्यूटर के व्यावहारिक पक्ष के लिए अपनी आँखें बंद करते हैं - आकार, वजन, मूल्य, गर्मी आदि, तो एक प्रोग्रामिंग भाषा वास्तव में क्या करने में सक्षम होनी चाहिए? आइए इस प्रश्न का अन्वेषण करें।

इस लेख में उदाहरणों को समझने के लिए, LISP (योजना) में कार्यों के बारे में बुनियादी अवधारणाओं की आवश्यकता है। यदि आप समझते हैं कि यह कोड क्या प्रिंट करेगा, तो आप सुरक्षित रूप से आगे पढ़ सकते हैं:

(define x 10) (define (fy) (display x) (newline) (display y) (newline) ) (define gf) (f 1) (g 2)

var x = 10; var f = function(y) { console.log(x); console.log(y); } var g = f; f(1); g(2);

यह लेख मस्तिष्क के लिए सिर्फ एक कसरत है, न कि कुछ ऐसा जो वास्तविक कोड में इस्तेमाल किया जा सकता है। लेकिन जिस तरह एक गिटारवादक तराजू बजाता है, जिसे वह कभी असली गाने में इस्तेमाल नहीं करता है, इसलिए प्रोग्रामर्स को समय-समय पर अपने दिमाग को स्ट्रेच करना चाहिए।

मैं प्रदर्शन के लिए योजना का उपयोग करूंगा, लेकिन कोई भी अन्य भाषा जो फ़र्स्ट-क्लास फ़ंक्शंस और लेक्सिकल स्कोप (क्लोज़र, मुख्य रूप से) के रूप में फ़ंक्शंस का समर्थन करती है।

यदि आप पहले से ही ऐसी चीजें देख चुके हैं (शायद SICP या द लिटिल शेमर में), तो आपको अपने लिए कुछ नया करने की तलाश में कोड पर जाना चाहिए।

अगर आपने पहले ऐसा कुछ नहीं देखा है, तो आपके लिए कुछ स्वादिष्ट है। पहली बार, सब कुछ बेहद अजीब लगेगा। धीरे-धीरे हटो। पिछले वाले को समझने के बाद ही अगले भाग पर आगे बढ़ें। यहां उल्लिखित अवधारणाएं सहज नहीं लग सकती हैं, लेकिन वे बहुत सरल भागों से निर्मित हैं।

और अंत में: यदि आप किसी जगह फंस गए हैं, तो निराशा न करें। कागज पर एक फ़ंक्शन के प्रदर्शन को ट्रैक करना यह समझने का एक बहुत अच्छा तरीका हो सकता है कि यह कैसे काम करता है (मैं आरामदायक लेखन के लिए एक अच्छा पोर्टेबल डेस्क खरीदने की सलाह देता हूं)। यदि यह मदद नहीं करता है, तो बस लेख को बंद करें और कल पढ़ने के लिए वापस आ जाएं। कभी-कभी नई अवधारणाओं को अपना स्थान खोजने से पहले अपने सिर में थोड़ा भटकना पड़ता है।

• सूचियों
  
  • if से सूची
  • लेकिन डेटा कहां गया?
  • इन नींवों पर निर्माण
    
    • नक्शा
    • फिल्टर
    • और, या, नहीं
    
    
  • लंबोदर कार्यों की सूची
  
  
• संख्या
  
  • एक संख्या क्या है?
  • inc, dec
  • is_zero
  • जोड़ना
  • उप
  • उप प
  • is_equal
  • कम_थाना, बड़ा_थाना
  
  
• सर्कल को बंद करना
  
  • n वें
  • छोड़ो, ले लो
  • लंबाई
  
  
• निष्कर्ष

1 सूची

ठीक है, चलो शुरू हो जाओ! प्रोग्रामर द्वारा सबसे अधिक निष्पादित प्रक्रियाओं में से एक डेटा ग्रुपिंग है। इसके लिए स्कीम में बिल्ट-इन लिस्ट हैं (अन्यथा यह LISP नहीं होगा;):

(define names (list "Alice" "Bob" "Candice"))

var names = ["Alice", "Bob", "Candice"];

लेकिन क्या होगा अगर स्कीम में कोई सूची न हो? क्या हम उन्हें, या उनके समान कुछ बना सकते हैं?

इस प्रश्न का उत्तर देने के लिए, आइए उन चीजों के न्यूनतम सेट के बारे में सोचें, जिन्हें हमें एक सूची की तरह बनाने की आवश्यकता है। ऐसा करने के कई तरीके हैं, लेकिन हम उनमें से केवल एक पर विचार करेंगे।

सूची के साथ काम करने के लिए, हमें चार चीजें चाहिए:

• एक "खाली सूची" की अवधारणा
  
• सूची के शीर्ष पर एक आइटम जोड़ने का तरीका
  
• किसी सूची में पहला आइटम प्राप्त करने का तरीका
  
• सूची के पहले तत्व को छोड़कर सब कुछ प्राप्त करने का एक तरीका
  

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

इन चार भागों को लागू करने के कई तरीके हैं - मैं कार्यों का उपयोग करूंगा। ये रहा उनका स्केच:

(define empty_list '()) (define (prepend el lst) ...) (define (head lst) ...) (define (tail lst) ...) (define (is_empty lst) ...)

var empty_list = null; var prepend = function(el, list) { // ... }; var head = function(list) { // ... }; var tail = function(list) { // ... }; var is_empty = function(list) { // ... };

इनमें से प्रत्येक परिभाषा का वर्णन यहां दिया गया है।

empty_list शून्य तत्वों की सूची का प्रतिनिधित्व करने वाला एक विशेष मूल्य है। यह कुछ भी हो सकता है, इसलिए मैं योजना से मानक '() उपयोग करूंगा। हम बाद में इस पर वापस आएंगे।

(prepend 1 some_list) एक नई सूची लौटाएगा जो अपनी शुरुआत में डाले गए 1 साथ पुराने जैसा दिखता है। इसलिए, यदि हम संख्या 1 और 2 की सूची बनाना चाहते हैं, तो हम लिख सकते हैं (prepend 1 (prepend 2 empty_list)) , या "खाली सूची में 1 जोड़ने के परिणाम में 2 जोड़ें"

(head some_list) सूची में पहला आइटम लौटाएगा। एक खाली सूची से head परिणाम परिभाषित नहीं किया जाता है, इसलिए आपको सावधान रहने और ऐसा करने की आवश्यकता नहीं है!

(tail some_list) एक नई सूची लौटाएगा जो पहले तत्व के बिना पुराने की तरह दिखती है। फिर से, खाली सूची से कॉलिंग tail सब कुछ बर्बाद कर देगा।

(is_empty some_list) #t को वापस करेगा यदि यह सूची खाली है और #f अन्यथा।

एक बार जब हमारे पास ये चार कार्य होते हैं (साथ ही एक खाली सूची के लिए एक विशेष अर्थ), हम उनके आधार पर चीजों का निर्माण शुरू कर सकते हैं, तो आइए जानें कि उन्हें कैसे लागू किया जाए!

1.1 If से सूची

आप सोच सकते हैं कि आप cdr , car और cdr उपयोग कर सकते हैं, लेकिन यह लेख यह जानने के लिए एक प्रयोग है कि हमें वास्तव में क्या चाहिए, चलो भाषा की अंतर्निहित विशेषताओं का उपयोग न करें यदि इसे टाला जा सकता है।

इसलिए, अगर हम भाषा की क्षमताओं का उपयोग नहीं करना चाहते हैं, तो हमारे लिए क्या रह गया है? खैर, अभी के लिए, हमारे पास केवल फ़ंक्शन (और '() ) हैं, तो चलो उन्हें आज़माएं!

सूचियों के कार्यान्वयन का पहला कार्य संस्करण यहां दिया गया है:

(define empty_list '()) (define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) ) (define (head lst) (lst "head") ) (define (tail lst) (lst "tail") ) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } }; var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); }; var is_empty = function(list) { return list === null; };

अपने पसंदीदा स्कीम दुभाषिया में इसे चिपकाएँ और चारों ओर खेलें:

(define e empty_list) (display (is_empty e)) ; #t (define names (prepend "Alice" (prepend "Bob" (prepend "Candice" empty_list ) ) ) ) (display (is_empty names)) ; #f (display (head names)) ; Alice (display (tail names)) ; Some function representing the list of ("Bob", "Candice") (display (head (tail names))) ; Bob

var e = empty_list; console.log(is_empty(e)); // true var names = prepend("Alice", prepend("Bob", prepend("Candice", empty_list))); console.log(is_empty(names)); // False console.log(head(names)); // Alice console.log(tail(names)); // Some function representing the list of ("Bob", "Candice") console.log(head(tail(names))); // Bob

1.2 लेकिन डेटा कहां गया?

इन विशेषताओं की परिभाषाओं ने आपको चौंका दिया? सूची इस तरह के एक महत्वपूर्ण, वस्तु-उन्मुख अवधारणा की तरह लगती हैं, लेकिन केवल कार्य हैं!

आइए देखें कि वे वास्तव में कैसे काम करते हैं। शुरुआत के लिए, "खाली सूची" की अवधारणा बहुत सीधी है:

(define empty_list '()) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var is_empty = function(list) { return list === null; };

आप किसी भी मूल्य का चयन कर सकते हैं। '() उपयुक्त है, इसलिए मैंने इसका इस्तेमाल किया।

अब सबसे महत्वपूर्ण prepend : प्रस्तुत करना।

(define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) )

var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } };

यहीं पर सारा जादू होता है। इसे खत्म करने की सोचते हैं।

सबसे पहले, हम जानते हैं कि जब हम सूची के शीर्ष पर कुछ जोड़ते हैं, तो हमें (नई) सूची वापस मिलती है। तो prepend का रिटर्न मान एक सूची होना चाहिए।

कोड पर एक नज़र यह समझने के लिए पर्याप्त है कि prepend एक फ़ंक्शन देता है। तो, हमारे छोटे विचार प्रयोग में, एक सूची सिर्फ एक (लंबो-) योजना कार्य है!

तो हमें सूचियों के साथ क्या करने की आवश्यकता है (शून्य के लिए जाँच के अलावा जो हमने पहले से ही कवर किया है)? खैर, हमें सिर और पूंछ प्राप्त करने की आवश्यकता है। जब हम कॉल करते हैं (prepend ht) , हम सिर्फ तर्क के रूप में सिर और पूंछ पास करते हैं! इसलिए, prepend हम एक फ़ंक्शन लौटाते हैं जो जानता है कि अनुरोध पर उसके सिर या पूंछ को कैसे वापस किया जाए।

तो, एक "सूची" एक फ़ंक्शन है "जो जानता है कि मांग पर अपना सिर या पूंछ कैसे प्राप्त करें।" यह पता चला है कि हमारे head और tail कार्यों को केवल अच्छी तरह से पूछा जाना चाहिए!

(define (head lst) (lst "head") ) (define (tail lst) (lst "tail") )

var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); };

वह सब है! हमने कुछ नहीं बल्कि कार्यों का उपयोग करते हुए कोड की 24 लाइनों में एक सूची बनाई। इससे पहले कि आप आगे बढ़ें, सुनिश्चित करें कि आप समझते हैं कि यह क्यों काम करता है। आप कागज के एक टुकड़े पर अभ्यास कर सकते हैं।

1.3 इस नींव पर निर्माण

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

नक्शा

सूचियों पर सामान्य कार्यों में से एक पुराने के माध्यम से लूपिंग और प्रत्येक तत्व के लिए कुछ फ़ंक्शन लागू करके एक नया बनाना है। इसे map कहा जाता है।

(define (map fn l) (if (is_empty l) empty_list (prepend (fn (head l)) (map fn (tail l))) ) )

var map = function(fn, l) { if (is_empty(l)) { return empty_list; } else { return prepend(fn(head(l)), map(fn, tail(l))); } };

यदि आप इस तरह की परिभाषाओं को पुनरावृत्ति करने के लिए उपयोग नहीं कर रहे हैं, तो आप कुछ मिनट बिताना चाहते हैं और यह काम करते हैं कि कैसे पेंट कर सकते हैं। उदाहरण के लिए, इस तरह:

(define (square x) (* xx)) (define numbers (prepend 1 (prepend 2 (prepend 3 empty_list)))) (define squared_numbers (map square numbers)) ; (map square (1 2 3)) ; (prepend (square 1) (map square (2 3)) ; (prepend (square 1) (prepend (square 2) (map square (3)))) ; (prepend (square 1) (prepend (square 2) (prepend (square 3) (map square '())))) ; (prepend (square 1) (prepend (square 2) (prepend (square 3) '()))) ; (prepend (square 1) (prepend (square 2) (prepend 9 '()))) ; (prepend (square 1) (prepend (square 2) (9))) ; (prepend (square 1) (prepend 4 (9))) ; (prepend (square 1) (4 9)) ; (prepend 1 (4 9)) ; (1 4 9)

var square = function(x) { return x * x; } var numbers = prepend(1, prepend(2, prepend(3, empty_list))); var squared_numbers = map(square, numbers); // map(square, [1, 2, 3]) // prepend(square(1), map(square, [1, 2, 3])) // prepend(square(1), prepend(square(2), map(square, [3]))) // prepend(square(1), prepend(square(2), prepend(square(3), map(square, [])))) // prepend(square(1), prepend(square(2), prepend(square(3), []))) // prepend(square(1), prepend(square(2), prepend(9, []))) // prepend(square(1), prepend(square(2), [9])) // prepend(square(1), prepend(4, [9])) // prepend(square(1), [4, 9]) // prepend(1, [4, 9]) // [1, 4, 9]

मैं योजना-शैली सूची ( (1 2 3) ) लिखता हूं, लेकिन वास्तव में prepend से लौटाए गए कार्य हैं।

यदि आप अभी भी इसे समझ नहीं पाए हैं, तो निष्पादन को ट्रैक करें (map square empty_list) और फिर निष्पादन (map square (prepend 10 empty_list)) ।

इस शैली में पुनरावर्ती सोच के लिए कुछ अभ्यास की आवश्यकता होती है। मेरे पास नोटबंदी का एक झुंड है, जो इस से जुड़ा है। अनुभवी गिटारवादक नई सामग्री को धीरे-धीरे और व्यवस्थित रूप से सीखते हैं, और प्रोग्रामर के ऐसा नहीं करने का कोई कारण नहीं है। फ़ंक्शन कॉल की वृद्धि और विनाश को देखने से आपको यह समझने में मदद मिल सकती है कि ये चीजें वास्तव में कैसे काम करती हैं, जबकि लंबे समय तक कोड को देखने से कुछ भी नहीं होगा।

फिल्टर

अब हम थोड़ा तेज चलना शुरू करेंगे, लेकिन आपको अभी भी यह सुनिश्चित करने की आवश्यकता है कि आप आगे बढ़ने से पहले पूरी तरह से सब कुछ समझ लें। आप जितना चाहें उतना समय बिताएं, कागज पर लिखें, कोड चलाएं, इसे महसूस करें।

अगला फ़ंक्शन जो हम सूचियों पर बनाएंगे वह filter । यह एक फ़ंक्शन और एक सूची लेता है और मूल के उन तत्वों से युक्त एक नई सूची देता है जिसके लिए दिए गए फ़ंक्शन #t देता है। यहाँ एक उदाहरण है:

(define numbers (prepend 1 (prepend 2 (prepend 3 empty_list)))) (define (is_odd x) (equal? (modulo x 2) 1)) (filter is_odd numbers) ; (1 3)

var numbers = prepend(1, prepend(2, prepend(3, empty_list))); var is_odd = function(x) { return x % 2 === 1; } filter(is_odd, numbers); // [1, 3]

अब हम filter लागू filter :

(define (filter fn l) (if (is_empty l) empty_list (if (fn (head l)) (prepend (head l) (filter fn (tail l))) (filter fn (tail l)) ) ) )

var filter = function(fn, l) { if (is_empty(l)) { return empty_list; } else if (fn(head(l))) { return prepend(head(l), filter(fn, tail(l))); } else { return filter(fn, tail(l)); } };

ब्रेक लें, किसी भी उदाहरण के लिए जाँच करें। इसे पूरी तरह से समझकर ही आगे बढ़ें।

और, या, नहीं

हम पाठ्यक्रम से विचलित होते हैं और "सहायक" कार्यों को लागू करते हैं। वे सूचियों से संबंधित नहीं हैं, लेकिन हमें अभी भी उनकी आवश्यकता है।

(define (not x) (if x #f #t ) ) (define (and ab) (if a (if b #t #f ) #f ) ) (define (or ab) (if a #t (if b #t #f ) ) )

var not = function(x) { if (x) { return false; } else { return true; } }; var and = function(a, b) { if (a) { if (b) { return true; } else { return false; } } else { return false; } }; var or = function(a, b) { if (a) { return true; } else { if (b) { return true; } else { return false; } } };

स्वाभाविक रूप से, योजना में पहले से ही यह सब है, लेकिन हम सभी प्रकार की भाषा सुविधाओं का उपयोग करने से बचने की कोशिश कर रहे हैं यदि हम उनके बिना कर सकते हैं। हम कार्यों के साथ कितनी दूर जा सकते हैं और if ?

थोड़ा ध्यान दें: ये सिर्फ सामान्य योजना के कार्य हैं, इसलिए (and ab) शॉर्ट-इन गणना का उपयोग नहीं करते हैं जैसे बिल्ट-इन मैक्रो। यह हमारे लक्ष्यों को चोट नहीं पहुंचाएगा, लेकिन इसके बारे में मत भूलना।

1.4 लंबोदर कार्यों की सूची

अब, थोड़ा अभ्यास होने पर, हम अपने कार्यों की परिभाषाओं पर फिर से लौटेंगे:

(define empty_list '()) (define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) ) (define (head lst) (lst "head") ) (define (tail lst) (lst "tail") ) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } }; var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); }; var is_empty = function(list) { return list === null; };

इस कार्यान्वयन में, मुझे कुछ बातों की परवाह है। हमारा लक्ष्य यथासंभव कम से कम भाषा सुविधाओं का उपयोग करना है, लेकिन हमने पहले ही पर्याप्त उपयोग कर लिया है! मैं कम से कम पाँच गिन सकता हूँ:

• कार्यों
  
• if हालत
  
• पंक्तियां
  
• बूलियन मान ( #f और #t , परिणाम is_empty )
  
• समानता परीक्षण ( equal? )
  

यह पता चला है कि हम लगभग सभी से छुटकारा पा सकते हैं, लेकिन केवल पठनीयता (और मानसिक तनाव) की कीमत पर।

चलो स्ट्रिंग्स, समानता जांच से छुटकारा पाएं, और भले if पहले निर्माण करें:

(define (prepend el lst) (lambda (selector) (selector el lst) ) ) (define (head lst) (lst (lambda (ht) h)) ) (define (tail lst) (lst (lambda (ht) t)) )

var prepend = function(el, list) { return function(selector) { return selector(el, list); }; }; var head = function(list) { return list(function(h, t) { return h; }); }; var tail = function(list) { return list(function(h, t) { return t; }); };

इससे पहले कि आप यह पता लगाने की कोशिश करें, आपको एक काटने चाहिए! कोई रेखाएं नहीं हैं, समानता के लिए कोई जांच नहीं if , if नहीं, लेकिन आपके पास अभी भी सूची है!

prepend फ़ंक्शन एक फ़ंक्शन देता है, जैसे पिछले संस्करण में "सूची" वास्तव में एक फ़ंक्शन था जो अनुरोध पर अपने सिर और पूंछ को वापस करना जानता था।

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

चलो head समारोह को देखो:

• head लिस्ट और कॉल्स (list ...) स्वीकार करता है, जिसका अर्थ है "अरे, लिस्ट, कृपया अपना सारा डेटा इस छोटे से फंक्शन को पास करें जो इसे देता है।"
  
• सूची कॉल करती है (... el lst) , जिसका अर्थ है "ठीक है, छोटा कार्य, यहां आपके पास मेरा सिर और पूंछ है।"
  
• सहायक कार्य वास्तव में (lambda (ht) h) , जिसका अर्थ है जब इसे सिर और पूंछ के साथ तर्क के रूप में कहा जाता है, तो यह सिर को लौटाता है।
  
• head परिणाम लेता है और इसे सीधे कॉलिंग फ़ंक्शन में भेजता है।
  

tail बिल्कुल उसी तरह काम करती है, केवल उसका सहायक फ़ंक्शन दूसरा तर्क (पूंछ) लौटाता है, और पहला नहीं।

वह सब है! समानता के लिए जाँच करता है और if गायब हो गया है। क्या आप बता सकते हैं कि वे कहां गए थे? अब उनके बदले क्या?

आगे बढ़ने से पहले, एक खाली सूची के कार्यान्वयन को साफ करते हैं। वह अभी भी '() और समानता चेक का उपयोग करती है। हम उन्हें हटाते हैं और सब कुछ कमोबेश समान बनाते हैं।

ऐसा करने के लिए, आपको अन्य कार्यों को थोड़ा बदलने की आवश्यकता है, लेकिन यदि आप इस बिंदु तक सब कुछ समझते हैं, तो यह परिवर्तन मुश्किल नहीं होगा।

(define (empty_list selector) (selector '() '() #t) ) (define (prepend el lst) (lambda (selector) (selector el lst #f) ) ) (define (head lst) (lst (lambda (hte) h)) ) (define (tail lst) (lst (lambda (hte) t)) ) (define (is_empty lst) (lst (lambda (hte) e)) )

var empty_list = function(selector) { return selector(undefined, undefined, true); }; var prepend = function(el, list) { return function(selector) { return selector(el, list, false); }; }; var head = function(list) { return list(function(h, t, e) { return h; }); }; var tail = function(list) { return list(function(h, t, e) { return t; }); }; var is_empty = function(list) { return list(function(h, t, e) { return e; }); };

हमने सूचियों को थोड़ा और स्मार्ट बनाया। सिर और पूंछ के लिए एक सहायक कार्य को व्यक्त करने में सक्षम होने के अलावा, वे अब बता सकते हैं कि क्या वे खाली हैं। हमने तीसरे तर्क को head और tail कार्यों को ध्यान में रखा (और अनदेखा) किया, और हमने is_empty फ़ंक्शन को भी शेष के समान बनाया।

अंत में, हमने एक विशेष जादुई अर्थ के बजाय सभी के रूप में उसी भावना में empty_list को फिर से परिभाषित किया। खाली सूची अब हमेशा की तरह एक ही है - यह एक फ़ंक्शन है जो दूसरे को लेता है और इसे कहता है: "मेरा सिर और पूंछ '() और मैं एक खाली सूची हूं।"

मैंने '() उपयोग किया, क्योंकि मुझे स्कीम में कुछ भी बेहतर नहीं लगा, लेकिन आप अपनी इच्छानुसार किसी अन्य मूल्य का उपयोग कर सकते हैं। चूँकि हम खाली सूची से head या tail नहीं लगाने के लिए सावधान रहेंगे, ये मूल्य वैसे भी कभी भी पॉप नहीं होंगे।

अंत में, हमने केवल दो चीजों के साथ सूचियों के मूल तत्वों को लागू किया:

• कार्यों
  
• #t और #f रिक्त सूचियों के लिए।
  

यदि आप चाहते हैं, तो इस बारे में सोचें कि आप दूसरे से कैसे छुटकारा पा सकते हैं (और इस मामले में, क्या आप वास्तव में छुटकारा पा रहे हैं, या क्या आप केवल कुछ योजना सुविधा का उपयोग कर रहे हैं?)।

2 नंबर

prepend , head और tail की परिभाषाएं बहुत मस्तिष्क-भयावह दिखती हैं। हालाँकि, map और filter की परिभाषाएँ पहले से अधिक सीधी हैं।

इसका कारण यह है क्योंकि हमने उन पहले चार कार्यों में सूचियों के कार्यान्वयन विवरण को छिपा दिया था। हमने लगभग कुछ भी नहीं से सूची बनाने के सभी गंदे काम किए, और फिर इसे एक साधारण prepend , head और tail इंटरफ़ेस के पीछे छिपा दिया।

सरल घटकों से कुछ चीजें बनाने और उन्हें "ब्लैक बॉक्स" में बदलने का विचार कंप्यूटर विज्ञान और प्रोग्रामिंग के सबसे महत्वपूर्ण विचारों में से एक है, तो चलिए थोड़ा और आगे बढ़ते हैं और संख्याओं को लागू करते हैं।

2.1 एक संख्या क्या है?

इस लेख में, हम केवल गैर-ऋणात्मक संख्याओं पर विचार करेंगे। आप स्वयं नकारात्मक संख्याओं के लिए समर्थन जोड़ने का प्रयास कर सकते हैं।

हम किसी संख्या का प्रतिनिधित्व कैसे कर सकते हैं? ठीक है, जाहिर है, आप स्कीम नंबर का उपयोग कर सकते हैं, लेकिन यह इतना अच्छा नहीं है, क्योंकि हम इस्तेमाल की जाने वाली भाषा सुविधाओं की संख्या को कम करने की कोशिश कर रहे हैं।

संख्या का प्रतिनिधित्व करने का एक तरीका एक सूची है जिसकी लंबाई उस संख्या के बराबर है। हम कह सकते हैं कि (1 1 1) अर्थ है "तीन", ("cats" #f) अर्थ है "दो", और '() अर्थ है "शून्य"।

इस सूची के तत्वों का खुद से कोई मतलब नहीं है, तो चलिए कुछ ऐसा लेते हैं जो पहले से मौजूद है: एक खाली सूची! इसे महसूस करें:

(define zero empty_list) ; '() (define one (prepend empty_list empty_list)) ; ( '() ) (define two (prepend empty_list (prepend empty_list empty_list))) ; ( '() '() )

var zero = empty_list; // [] var one = prepend(empty_list, empty_list); // [ [] ] var two = prepend(empty_list, prepend(empty_list, empty_list)); // [ [], [] ]

2.2 inc, dec

हम अपने नंबरों के साथ कुछ करना चाहते हैं, तो चलिए उन कार्यों को लिखते हैं जो संख्याओं की सूची प्रतिनिधित्व के साथ काम करते हैं।

हमारी मुख्य निर्माण सामग्री inc और dec (वेतन वृद्धि) है।

(define (inc n) (prepend empty_list n) ) (define (dec n) (tail n) )

var inc = function(n) { return prepend(empty_list, n); }; var dec = function(n) { return tail(n); };

एक नंबर में एक जोड़ने के लिए, हम बस सूची में एक और तत्व सम्मिलित करते हैं। तो, (inc (inc zero)) अर्थ है दो।

एक को घटाने के लिए, हम बस तत्वों में से एक को हटा देते हैं: (dec two) अर्थ है "एक" (यह मत भूलो कि हम नकारात्मक संख्याओं को अनदेखा करते हैं)।

२.३ is_zero है

सूचियों के साथ काम करने की शुरुआत में, हम अक्सर is_empty उपयोग is_empty , इसलिए is_zero फ़ंक्शन भी किया जाना चाहिए:

(define (is_zero n) (is_empty n) )

var is_zero = function(n) { return is_empty(n); };

शून्य सिर्फ एक खाली सूची है!

2.4 जोड़ें

एक इकाई जोड़ना सरल है, लेकिन हम सबसे अधिक संभावना है कि मनमानी संख्याओं को जोड़ने में सक्षम होना चाहते हैं। अब, inc और dec , ऐसा करना बहुत आसान है:

(define (add ab) (if (is_zero b) a (add (inc a) (dec b)) ) )

var add = function(a, b) { if (is_zero(b)) { return a; } else { return add(inc(a), dec(b)); } };

यह एक और पुनरावर्ती परिभाषा है। संख्याओं को जोड़ते समय, दो संभावनाएँ उत्पन्न होती हैं:

• यदि b शून्य है, तो परिणाम सिर्फ a
  
• अन्यथा, a और b को जोड़ना a+1 और b-1 को जोड़ने के समान है
  

अंत में, b "एंड" होगा और उत्तर a होगा (जो कि b रूप में बढ़ा है)।

कृपया ध्यान दें कि सूचियों के बारे में एक शब्द नहीं है! "नंबर सूचीबद्ध हैं" की जानकारी is_zero , inc और dec पीछे छिपी हुई है, ताकि हम इसे अनदेखा कर सकें और "संख्या" के अमूर्त स्तर पर काम कर सकें।

2.5 उप

घटाव इसके अलावा के समान है, लेकिन जैसे ही b घटता है, हम दोनों को एक साथ कम कर देंगे:

(define (sub ab) (if (is_zero b) a (sub (dec a) (dec b)) ) )

var sub = function(a, b) { if (is_zero(b)) { return a; } else { return sub(dec(a), dec(b)); } };

अब हम कुछ लिख सकते हैं (add two (sub three two)) जैसे (add two (sub three two)) और परिणाम हमारे सिस्टम में संख्या "तीन" का प्रतिनिधित्व करेगा (जो, निश्चित रूप से, तीन तत्वों की एक सूची है)।

एक पल के लिए रुकें और याद रखें कि संख्याओं के अंदर वास्तव में सूचियां हैं, और सूचियों के अंदर कार्यों के अलावा कुछ भी नहीं है।हम संख्याओं को जोड़ और घटा सकते हैं, और इस सब के अंदर, बस आगे और पीछे घूमते हुए कार्य करते हैं, अन्य कार्यों में विस्तार करते हैं और जैसे ही आप कॉल करते हैं सिकुड़ते हैं, और लैम्ब्डा का यह wriggling गुच्छा किसी तरह का प्रतिनिधित्व करता है 1+1=2। कूल!

2.6 mul, pow

प्रशिक्षण के लिए, हम संख्याओं के गुणन को लागू करते हैं:

(define (mul ab) (if (is_zero b) zero (add a (mul a (dec b))) ) )

var mul = function(a, b) { if (is_zero(b)) { return zero; } else { return add(a, mul(a, dec(b))); } };

उपलब्धता addकार्य को बहुत सरल बनाती है। 3 * 4 3 + 3 + 3 + 3 + 0 के समान है। फ़ंक्शन के प्रदर्शन को कागज के एक टुकड़े पर ट्रैक करें यदि जो हो रहा है उसका अर्थ आपसे दूर जाना शुरू कर देता है, और जब आपको लगता है कि आप तैयार हैं तो वापस आ जाएं।

pow(घातांक) समान है mul, लेकिन संख्या की प्रतियों को जोड़ने के बजाय, हम उन्हें गुणा करेंगे, और पुनरावृत्ति का "आधार" एक होगा, शून्य नहीं।

(define (pow ab) (if (is_zero b) one (mul a (pow a (dec b))) ) )

var pow = function(a, b) { if (is_zero(b)) { return one; } else { return mul(a, pow(a, dec(b))); } };

2.7 is_equal है

संख्याओं के बारे में एक और समस्या एक समानता परीक्षण है, तो चलिए इसे लिखते हैं:

(define (is_equal nm) (if (and (is_zero n) (is_zero m)) #t (if (or (is_zero n) (is zero m)) #f (is_equal (dec n) (dec m)) ) ) )

var is_equal = function(n, m) { if (and(is_zero(n), is_zero(m))) { return true; } else if (or(is_zero(n), is_zero(m))) { return false; } else { return is_equal(dec(n), dec(m)); } };

तीन मामले हैं:

• यदि दोनों संख्याएँ शून्य हैं, तो वे समान हैं
  
  
• यदि एक और केवल एक संख्या शून्य है, तो वे समान नहीं हैं
  
  
• अन्यथा, प्रत्येक से एक घटाएं और फिर से प्रयास करें
  
  

जब इस फ़ंक्शन को दो गैर-शून्य तर्कों के साथ कहा जाता है, तो दोनों तब तक कम हो जाएंगे जब तक कि उनमें से कोई एक "पहले" समाप्त नहीं होता है, या वे एक ही समय में "अंत" करते हैं।

2.8 कम_थाना, बड़ा_थान

इसी तरह, आप लागू कर सकते हैं less_than:

(define (less_than ab) (if (and (is_zero a) (is_zero b)) #f (if (is_zero a) #t (if (is_zero b) #f (less_than (dec a) (dec b)) ) ) ) )

var less_than = function(a, b) { if (and(is_zero(a), is_zero(b))) { return false; } else if (is_zero(a)) { return true; } else if (is_zero(b)) { return false; } else { return less_than(dec(a), dec(b)); } };

इसके विपरीत is_equal, चार मामले हैं:

• यदि दोनों संख्याएं शून्य हैं, तो aकिसी से कम नहींb
  
• अन्यथा, यदि a(और केवल a) शून्य के बराबर है, तो यह उससे कम हैb
  
• अन्यथा, यदि b(और केवल b) शून्य के बराबर है, तो aयह इससे कम नहीं हो सकता है b(नकारात्मक संख्याओं पर विचार नहीं किया जाता है)
  
• अन्यथा, दोनों को कम करें और फिर से प्रयास करें।
  

और फिर से, दोनों संख्याएं कम से कम तब तक घटती हैं जब तक कि उनमें से कम से कम "समाप्त" नहीं हो जाता है, और तुलना का नतीजा निर्धारित होता है कि उनमें से कौन पहले "समाप्त" हुआ।

एक ही के लिए कुछ कर सकता है greater_than, लेकिन एक सरल तरीका है:

(define (greater_than ab) (less_than ba) )

var greater_than = function(a, b) { return less_than(b, a); };

2.9 डिव, मॉड

अब हमारे पास यह है less_than, हम विभाजन को लागू कर सकते हैं और शेष:

(define (div ab) (if (less_than ab) zero (inc (div (sub ab) b)) ) ) (define (rem ab) (if (less_than ab) a (rem (sub ab) b) ) )

var div = function(a, b) { if (less_than(a, b)) { return zero; } else { return inc(div(sub(a, b), b)); } }; var rem = function(a, b) { if (less_than(a, b)) { return a; } else { return rem(sub(a, b), b); } };

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

3 सर्कल को बंद करना

आज तक, हमारे पास पहले से ही एक (बहुत बुनियादी) काम करने वाली संख्या प्रणाली है, जो सूचियों पर निर्मित है। आइए शुरुआत में वापस जाएं और संख्याओं का उपयोग करने वाले अन्य सूची कार्यों को लागू करें।

3.1 nth

nसूची के ith तत्व को प्राप्त करने के लिए, हम बस उसमें से तत्वों को निकाल देंगे और nशून्य तक पहुंचने तक संख्या को कम कर देंगे :

(define (nth ln) (if (is_zero n) (head l) (nth (tail l) (dec n)) ) )

var nth = function(l, n) { if (is_zero(n)) { return head(l); } else { return nth(tail(l), dec(n)); } };

वास्तव में, अब हमारे पास दो सूचियां हैं, जिनमें से हम जिस तत्व को हटाते हैं, हम उसके माध्यम से जाते हैं, क्योंकि nयह एक संख्या है जो एक सूची है, और decइसमें से एक तत्व निकालता है। लेकिन सूचियों के कार्यान्वयन के अमूर्त होने पर पढ़ना बहुत अच्छा है, क्या यह नहीं है?

३.२ बूंद, लेना

आइए सूचियों के साथ काम करने के लिए दो उपयोगी कार्य करें - dropऔर take।

(drop l three)पहले तीन तत्वों के बिना एक सूची लौटाएगा।

(take l three)सूची के पहले तीन तत्वों को वापस करेगा।

(define (drop ln) (if (is_zero n) l (drop (tail l) (dec n)) ) ) (define (take ln) (if (is_zero n) empty_list (prepend (head l) (take (tail l) (dec n))) ) )

var drop = function(l, n) { if (is_zero(n)) { return l; } else { return drop(tail(l), dec(n)); } }; var take = function(l, n) { if (is_zero(n)) { return empty_list; } else { return prepend(head(l), take(tail(l), dec(n))); } };

3.3 टुकड़ा

सूची "स्लाइस" लागू होते ही एक बहुत ही सरल कार्य बन जाता है drop, takeऔर संख्याओं का घटाव:

(define (slice l start end) (take (drop l start) (sub end start)) )

var slice = function(l, start, end) { return take(drop(l, start), sub(end, start)); };

सबसे पहले, हम पहले सब कुछ छोड़ देते हैं start, और फिर वांछित संख्या तत्वों का चयन करते हैं।

३.४ लंबाई

हम निर्धारित कर सकते हैं length- सूची की लंबाई - पुनरावर्ती, सब कुछ की तरह:

(define (length l) (if (is_empty l) zero (inc (length (tail l))) ) )

var length = function(l) { if (is_empty(l)) { return zero; } else { return inc(length(tail(l))); } };

खाली सूची की लंबाई 0 है, और गैर-खाली सूची की लंबाई इसकी पूंछ की लंबाई से एक है।

यदि आपके विचार अभी तक एक मजबूत गाँठ में नहीं उलझ गए हैं, तो इस बारे में सोचें:

• सुविधाओं से बनी सूची
  
• नंबर उन सूचियों से बने होते हैं जिनकी लंबाई एक संख्या का प्रतिनिधित्व करती है
  
• length यह एक फ़ंक्शन है जो एक सूची लेता है और एक संख्या के रूप में अपनी लंबाई लौटाता है (एक सूची जिसकी लंबाई इस संख्या के बराबर है)
  
• और केवल अब हमने निर्धारित किया है length, हालांकि हम संख्याओं का उपयोग कर रहे हैं (जो संख्या का प्रतिनिधित्व करने के लिए सूची की लंबाई का उपयोग करते हैं) काफी समय तक!
  

क्या आपको पहले से चक्कर आ रहा है? यदि नहीं, तो इसे देखें:

(define mylist (prepend empty_list (prepend empty_list empty_list ) ) ) (define mylistlength (length mylist))

var mylist = prepend(empty_list, prepend(empty_list, empty_list)); var mylistlength = length(mylist);

mylistयह दो खाली सूची की सूची है।

mylistlengthयह लंबाई है mylist...

कि "दो" हैं ...

जिन्हें दो खाली सूची की सूची द्वारा दर्शाया गया है ...

और यह है mylist!

4 निष्कर्ष

अगर आपको यह छोटी सी भ्रमित करने वाली कहानी पसंद आई, तो मैं आपको द लिटिल स्कीमर पढ़ने की अत्यधिक सलाह देता हूं । यह पहली किताबों में से एक है जिसने वास्तव में प्रोग्रामिंग की मेरी समझ को बदल दिया है। डरो मत कि वहाँ योजना का उपयोग किया जाता है - भाषा वास्तव में मायने नहीं रखती है।

मैंने लेख से सभी कोड के साथ जीआईएसटी (मूल जावास्क्रिप्ट उदाहरण यहां भी बनाया है )। बेझिझक इसे कांटे और प्रयोग के लिए प्रयोग करें।

इसके अलावा, पुनरावर्ती कार्यों का अभ्यास करने के लिए, आप निम्नलिखित को लागू कर सकते हैं:

• append - सूची के अंत में एक आइटम जोड़ना
  
• concat - दो सूचियों का संयोजन
  
• minऔर max- दो संख्याओं के छोटे (बड़े) का पता लगाना
  
• remove- उसी के रूप में filter, केवल उन तत्वों की एक सूची देता है जिन पर परीक्षण फ़ंक्शन (विधेय) लौटता है#f
  
• contains_number - यह जांचना कि क्या कोई संख्या सूची से संबंधित है
  

या, यदि आप कुछ अधिक गंभीर चाहते हैं, तो पहले से निर्मित लोगों के आधार पर बड़ी अवधारणाओं को लागू करें:

• ऋणात्मक संख्या
  
• गैर-नकारात्मक तर्कसंगत संख्या
  
• ऋणात्मक परिमेय संख्या
  
• सहयोगी सूची
  

याद रखें, बिंदु कुछ ऐसा बनाने के लिए नहीं है जो वास्तविक कंप्यूटर पर अच्छी तरह से काम करता है। सही वोल्टेज लेने के लिए ट्रांजिस्टर और सर्किट का एक विशेष संयोजन कैसे प्राप्त करें, इसके बारे में सोचने के बजाय, एक सुंदर, परिपूर्ण, सार अर्थ में "कंप्यूटिंग" के बारे में सोचें।