73

मैं रिकर्सन स्कीम और कोरकर्सन स्कीम (कैटोमोर्फिम्स, एनामोर्फिज्म्स, हाइलोमोर्फिज्म इत्यादि) के कुछ वास्तव में सरल, आसानी से समझने के स्पष्टीकरण की तलाश में हूं, जिनके लिए बहुत सारे लिंक की आवश्यकता नहीं है, या एक श्रेणी सिद्धांत पाठ्यपुस्तक खोलना आवश्यक नहीं है। मुझे यकीन है कि मैंने इन योजनाओं में से कई को बेहोश कर दिया है और कोडिंग की प्रक्रिया के दौरान उन्हें अपने सिर में "लागू" किया है (मुझे यकीन है कि हम में से कई हैं), लेकिन मुझे कोई संकेत नहीं है कि (सह) रिकर्सन योजनाएं क्या हैं I उपयोग कहा जाता है। (ठीक है, मैंने झूठ बोला। मैं बस उनमें से कुछ के बारे में पढ़ रहा हूं, जिसने इस सवाल को प्रेरित किया। लेकिन आज से पहले, मुझे कोई सुराग नहीं था।)डमी के लिए रिकर्सन योजनाएं?

मुझे लगता है कि प्रोग्रामिंग समुदाय के भीतर इन अवधारणाओं का प्रसार बाधित हो गया है निषिद्ध स्पष्टीकरण और उदाहरणों में से एक को पार करना पड़ता है - उदाहरण के लिए विकिपीडिया पर, बल्कि अन्यत्र भी।

यह शायद उनके नामों से बाधित हो गया है। मुझे लगता है कि कुछ वैकल्पिक, कम गणितीय नाम हैं (केले और कटे हुए तार के बारे में कुछ?) लेकिन मुझे कोई संकेत नहीं है कि कटरियर नाम रिकर्सन योजनाओं के लिए क्या हैं जो मैं उपयोग करता हूं।

मुझे लगता है कि यह बाइनरी पेड़ जैसे अमूर्त डेटा प्रकारों की बजाय सरल वास्तविक दुनिया की समस्याओं का प्रतिनिधित्व करने वाले डेटाटाइप के उदाहरणों का उपयोग करने में मदद करेगा।

+5

जेरेमी गिबन्स के कई कागजात हैं जो सबसे अच्छे परिचय हो सकते हैं क्योंकि वे स्पष्ट हैं और बड़े पैमाने पर स्वयं निहित हैं। "स्ट्रीमिंग प्रतिनिधित्व परिवर्तक" (गुना और खुलासा हुआ संयुक्त), "प्रोग्राम समझ के लिए विखंडन" (पैरामोर्फिज्म और अधिक), "नीचे की सराहना की गई" (एनामोर्फिज्म)। http://www.cs.ox.ac.uk/people/publications/date/Jeremy.Gibbons.html –

उत्तर

37

बेहद कमजोर बोलते हुए, एक कैटमोर्फिज्म fold का थोड़ा सा सामान्यीकरण है, और एक एनामोर्फिज्म unfold का मामूली सामान्यीकरण है। (और एक हाइलोमोर्फिज्म सिर्फ एक गुना के बाद एक खुलासा है।)। श्रेणी सिद्धांत को स्पष्ट बनाने के लिए, आमतौर पर उन्हें अधिक कठोर रूप में प्रस्तुत किया जाता है। घनत्व फ़ॉर्म हमें डेटा (प्रारंभिक बीजगणित के आवश्यक रूप से परिमित उत्पाद) और कोडाटा (अंतिम कोयलाग्रा के संभवतः अनंत उत्पाद) को अलग करने देता है। यह भेद हमें गारंटी देता है कि एक गुना अनंत सूची पर कभी नहीं कहा जाता है। सामान्य रूप से कैटमोर्फिज्म और एनामोर्फिज्म के मजाकिया तरीके के लिए अन्य कारण यह है कि एफ-अल्जीब्रस और एफ-कोल्गेब्रस (मज़दूरों से उत्पन्न) पर काम करके हम उन्हें एक बार और एक बार सूची में एक बार लिख सकते हैं, एक बार बाइनरी पेड़, आदि। बदले में यह स्पष्ट रूप से स्पष्ट करने में मदद करता है क्यों वे सभी एक ही चीज़ हैं।

लेकिन एक शुद्ध अंतर्ज्ञान दृष्टिकोण से, आप कोटा और एना को कम करने और उत्पादन के रूप में सोच सकते हैं, और यह इसके बारे में है।

संपादित करें: थोड़ा अधिक

एक रूपांतरण (गिबन्स) एक के अंदर से बाहर hylo की तरह है - इसकी एक गुना एक प्रकट करना होता है। तो आप इसे एक धारा को फाड़ने और संभावित रूप से अलग संरचना के साथ एक नया निर्माण करने के लिए उपयोग कर सकते हैं।

Ekmett एक अच्छा "क्षेत्र गाइड" साहित्य में विभिन्न योजनाओं पर पोस्ट किया: http://comonad.com/reader/2009/recursion-schemes/

हालांकि, जबकि "सहज" स्पष्टीकरण स्पष्ट हैं, लिंक किए गए कोड बहुत कम है, और में से कुछ पर ब्लॉग पोस्ट ये जटिल/मनाई पक्ष पर एक टैड हो सकता है।

कहा जाता है कि शायद हिस्टोमोर्फिज्म के अलावा मुझे नहीं लगता कि बाकी चिड़ियाघर जरूरी है कि आप ज्यादातर समय सीधे सोचना चाहें। यदि आप हाइलो और मेटा "प्राप्त" करते हैं, तो आप अकेले उनके संदर्भ में लगभग कुछ भी व्यक्त कर सकते हैं। आम तौर पर अन्य morphisms अधिक प्रतिबंधक हैं, कम नहीं (लेकिन इसलिए आपको अधिक संपत्ति "मुक्त" देते हैं)।

+1

ठीक है, धन्यवाद, लेकिन यह सिर्फ तीन है - कुछ भी हैं। मुझे उम्मीद है कि कोई जवाब देगा जो कुछ अन्य रिकर्सन योजनाओं के बारे में है। –

+3

शेष बकाया रिकर्सन योजनाएं अधिकांश प्रकार के अस्पष्ट हैं, शायद पैरामोर्फिज्म को छोड़कर, जो उन विषयों के लिए "प्रेरण सिद्धांतों" के लिए काफी अच्छी तरह से मेल खाते हैं जिन्हें हम अक्सर निर्भर भाषाओं में देखते हैं। मुझे यह पता नहीं लगा है कि सभी श्रेणी सिद्धांत यहां कैसे काम करते हैं, लेकिन मुझे संदेह है कि यह बहुत भयंकर रूप से टूट जाएगा :) – copumpkin

+3

परफॉर्मिज्म एक गुना की तरह है लेकिन आप "शेष इनपुट" पर देख सकते हैं। एक गुना केवल आपको ट्रैवर्सल के दौरान प्राथमिक पहुंच देता है। –

21

कुछ संदर्भ, से सबसे श्रेणी-सैद्धांतिक (लेकिन एक "क्षेत्र नक्शा" आप से बचने "लिंक के बहुत सारे क्लिक" देंगे देने के लिए प्रासंगिक) सरल & अधिक आत्म निहित करने के लिए:

  • जहां तक ​​"केले & बार्बेड वायर" शब्दावली जाती है, यह the original paper of Meijer, Fokkinga & Patterson (और अन्य लेखकों द्वारा इसकी अगली कड़ी) से आता है, और यह कम प्यारा विकल्प के रूप में नोटेशन-भारी के रूप में समतुल्य है: "नाम" (केले , इत्यादि) उन निर्माणों के असीसी नोटेशन की ग्राफिकल उपस्थिति के लिए सिर्फ एक शॉर्टकट हैं जिन्हें वे देख रहे हैं। उदाहरण के लिए, catamorphisms (यानी folds) (| _ |) के साथ दर्शाए जाते हैं, और पैरा-साथ-कंस्ट्रैसिस "केले" जैसा दिखता है, इसलिए नाम। यह वह पेपर है जिसे अक्सर "अभेद्य" कहा जाता है, इसलिए यदि मैं आप थे तो पहली बात यह नहीं होगी कि मैं देखता हूं।

  • उन प्रत्यावर्तन योजनाओं के लिए बुनियादी संदर्भ (या अधिक सटीक, उन प्रत्यावर्तन योजनाओं के लिए एक संबंधपरक दृष्टिकोण के लिए) डी मूर के Algebra of Programming (किताब एक प्रिंट पर मांग के रूप में छोड़कर अनुपलब्ध है बर्ड & है, लेकिन उपलब्ध प्रतियां हैं दूसरे हाथ & यह पुस्तकालयों में होना चाहिए)। इसमें पॉइंट-फ्री प्रोग्रामिंग का विस्तृत स्पष्टीकरण & है, यदि अभी भी "अकादमिक" है: पुस्तक कुछ श्रेणी-सैद्धांतिक शब्दावली पेश करती है, हालांकि आत्मनिर्भर तरीके से। फिर भी, अभ्यास (जो आपको एक पेपर में नहीं मिलेगा) मदद करते हैं।

  • Sorting morphisms by Lex Augustjein, रिकर्सन योजनाओं को समझाने के लिए विभिन्न डेटा संरचनाओं पर सॉर्टिंग एल्गोरिदम का उपयोग करता है।

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

  • एक प्रतीकों से मुक्त प्रस्तुति बनाने के लिए एक और दृष्टिकोण The Fun of Programming में Jeremy Gibbons' chapter Origami Programming है, पिछले एक के साथ कुछ ओवरलैप के साथ। इसकी ग्रंथसूची इस विषय के परिचय का दौरा करती है।

    संपादित करें: Jeremy Gibbons बस मुझे बताएं कि उन्होंने इस प्रश्न को पढ़ने के बाद book's webpage पर पूरी पुस्तक की ग्रंथसूची में एक लिंक जोड़ा है। का आनंद लें!

मुझे डर है कि इन पिछले दो संदर्भ केवल का एक ठोस स्पष्टीकरण देने के कर रहा हूँ (cata | एना | hylo | पैरा) morphisms, लेकिन मेरी आशा व्यक्त की कि इस बीजीय रीतिवाद आप पा सकते हैं के माध्यम से आंसू करने के लिए पर्याप्त होगा अधिक नोटेशन में भारी प्रकाशन। मैं उन चारों के अलावा किसी भी सख्ती से गैर-श्रेणी-सैद्धांतिक स्पष्टीकरण (सह-) रिकर्सन योजनाओं के बारे में नहीं जानता।

15

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

http://www.timphilipwilliams.com/slides.html

वहाँ सभी सामान्य संदिग्धों के लिए संदर्भ (लेंस, केले, कार्टे आदि आला कांटेदार तार) स्लाइड के अंत में कर रहे हैं और आप भी "Origami प्रोग्रामिंग" गूगल सकता है जो है एक अच्छा परिचय है कि मैं पहले नहीं आया था।

और जब इसे अपलोड कर वीडियो यहाँ हो जाएगा:

http://www.youtube.com/user/LondonHaskell

संपादित सवाल में लिंक के सबसे ऊपर huitseeker के जवाब में हैं।

+1

यह आश्चर्यजनक है, धन्यवाद (और टिम)! – glaebhoerl

संबंधित मुद्दे