के माध्यम से कुशल सूची संलग्न/प्रीपेड करें कुछ महीने पहले मैंने ओ (1) में अन्य सूचियों में सूचियों को जोड़ने और प्रीपेड करने के लिए एक कुशल दृष्टिकोण को पढ़ा था, जिसमें फ़ंक्शन रचनाओं का प्रतिनिधित्व किया गया था, जिसे एक बार मूल्यांकन किया गया था, ओ (एन) परिणामस्वरूप सूची।फ़ंक्शन कंपोज़िशन
दुर्भाग्य से मैं इस आलेख के स्रोत या (यदि मौजूदा) इस तकनीक/दृष्टिकोण का नाम याद नहीं कर सकता। क्या आपके पास इसके बारे में संदर्भ हैं, कृपया?
डेटा संरचना को एक अंतर सूची कहा जाता है (या DList संक्षिप्त के लिए)। आप इसे in a library available on Hackage का डिफ़ॉल्ट कार्यान्वयन पा सकते हैं।
जैसा कि आपने बताया है, एक पूर्ण विवरण a chapter in Real World Haskell on the subject से एकत्र किया जा सकता है।
बढ़िया, धन्यवाद! यही वही है जो मैं खोज रहा था। 'डीएलआईस्ट' के लिए थोड़ी सी गुगलते हुए, मुझे पता चला कि मैं वास्तव में डॉन स्टीवर्ट द्वारा "रियल वर्ल्ड हास्केल" के अध्याय 13 की खोज कर रहा था ... यहां उन सूचियों का काम करने के बारे में पूर्ण स्पष्टीकरण है: http: // book। realworldhaskell.org/read/data-structures.html#data.dlist क्या आप भविष्य में संदर्भ के रूप में उत्तर में पुस्तक को एक लिंक डाल सकते हैं, कृपया? धन्यवाद –
यह भी LYAH में उल्लेख किया गया है: http://learnyouahaskell.com/for-a-few-monads-more, अध्याय "अंतर सूचियां" – efie
@ रिकार्डो मूल अंतर सूची निश्चित रूप से प्रोलॉग में पैदा हुई थी, और इसमें कुछ भी नहीं है एक सिंगल-लिंक्ड लिस्ट से अधिक जो पॉइंटर के आसपास अपने अंतिम विपक्षी सेल में भी है, इसलिए इसे कुशलतापूर्वक बढ़ाया जा सकता है। हास्केल में गैर-बैकट्रैकिंग प्रोलॉग में, एक बार पॉइंटर सेट होने पर इसे बदला नहीं जा सकता है। इसे आसानी से सी में कार्यान्वित किया जाता है और डेटा संरचना में एक और डेटा फ़ील्ड, * लंबाई * जोड़कर अपरिवर्तनीय दिखाई दे सकता है, इसलिए उस बिंदु से पहले कोई पहुंच नहीं है। इसे विस्तारित करने से नई प्रतिलिपि लेकिन समान अंतर्निहित सूची के साथ एक प्रतिलिपि बन जाएगी। (कार्यान्वयनकर्ता, एनबी!) :) –
आपको ShowS और प्रीलूड के दोस्तों के बारे में सोचना चाहिए। here देखें।
(संभावित) पहली उपस्थिति जॉन ह्यूजेस "लिस्ट्स का एक उपन्यास प्रतिनिधित्व और इसके आवेदन को 'रिवर्स' के लिए एक पेपर में था (मुझे विश्वास है कि वे इससे पहले लोककथा थे) - इसलिए उन्हें _ ह्यूजेस लिस्ट_ भी कहा जाता है। ध्यान दें कि वे केवल कुशल ** निर्माण ** का समर्थन करते हैं - हैकेज पर डीएलआईस्ट पैकेज में एपीआई का समर्थन _introspection_ है, लेकिन आत्मनिरीक्षण को लागू करने के लिए आपको नियमित सूची में बदलाव करना होगा और फिर से वापस जाना होगा। यह अक्षम है - यदि आप आत्मनिरीक्षण चाहते हैं तो आप एक अलग संरचना चाहते हैं। –
आत्मनिरीक्षण की आवश्यकता नहीं होने पर यह एक उचित पर्याप्त व्यापार है। यह इंगित करने के लिए धन्यवाद। मैं अभी उपयोग करने के लिए डेटा संरचना की तलाश नहीं कर रहा हूं, हालांकि, मैं अंतर/ह्यूजेस सूचियों के लिए कार्यान्वयन का अध्ययन करना चाहता था। –