प्रीस्कैड डेटा संरचनाओं का उपयोग करके हास्केल में ज्ञापन

Question

मुझे this answer और this wiki page को हास्केल में ज्ञापन के लिए उत्कृष्ट परिचय के लिए मिला है। हालांकि, वे मुझे अभी भी एक प्रश्न के साथ छोड़ देते हैं कि मुझे उत्तर देने की उम्मीद है:

ऐसा लगता है कि उपयोग की जाने वाली तकनीक के लिए आपको डेटा खोलने के लिए "खोलने" की आवश्यकता होती है (जैसा कि "आंतरिक के उपयोग में") आप अपने ज्ञापन को स्टोर करने के लिए उपयोग करते हैं। उदाहरण के लिए, 1 तालिका संरचना लागू करता है और 2section 3 में एक पेड़ लागू करता है। क्या पूर्व-निर्मित डेटा संरचना के साथ कुछ ऐसा करना संभव है? मान लीजिए, उदाहरण के लिए, आपको लगता है कि Data.Map वास्तव में कमाल है, और इस तरह के Map में आपके ज्ञात मानों को संग्रहीत करना चाहते हैं। क्या कोई पूर्व-निर्मित डेटा संरचना के साथ ज्ञापन तक पहुंच सकता है, जहां कोई संरचना को लागू नहीं करता है, बल्कि पूर्व-निर्मित एक का उपयोग करता है?

उम्मीद है कि कोई मुझे सामान्य रूप से कार्यात्मक ज्ञापन की मेरी गलतफहमी को सही तरीके से सोचने, या शायद अधिक संभावना के बारे में संकेत देगा।

संपादित करें: मैं एक ही रास्ता के लगता है कि यह क्या करने के लिए कर सकते हैं, लेकिन यह सब पर सुंदर नहीं है: यदि f :: a -> b, तो एक शायद आसानी से एक memoized संस्करण f' :: Map a b -> a -> (Map a b, b), जहां पहला तर्क Memoization भंडारण है बना सकते हैं, और आउटपुट जोड़ी में संभावित रूप से अद्यतन स्टोरेज और गणना मूल्य शामिल है। यह राज्य-गुजर निश्चित रूप से वह नहीं है जो मैं चाहता हूं (हालांकि मुझे लगता है कि इसे एक मोनैड में लपेटा जा सकता है, लेकिन 1 और 2 में दृष्टिकोण की तुलना में यह बहुत अधिक है।

संपादित करें 2: शायद यह मेरे वर्तमान तरीके (गलत) विचार को आजमाने और व्यक्त करने में मदद करता है। वर्तमान में, मैं बार-बार, अपने आप को खींचने के लिए, मेरे मर्जी के खिलाफ गैर समाधान

import qualified Data.Map as Map 
memo :: (Ord a) => [a] -> (a -> b) -> (a -> b) 
memo domain f = (Map.!) storage 
    where 
     storage = Map.fromList (zip domain (map f domain)) 

में लग रहे हैं और मैं इस पर टकटकी, और अधिक मुझे लगता है कि मैं कुछ बुनियादी गलत समझा गया है। आप देखते हैं, मुझे लगता है कि मेरा memo [True, False]1 के ज्ञापन के बराबर है।

Answer 1

यदि आप देखते हैं, डेटा। मेमोकॉम्बिनेटर्स वास्तव में "पूर्व-निर्मित" डेटा पर निर्भर करता है। INTTrie। मुझे यकीन है कि आप एक ही कोड ले सकते हैं और इंट्री के उपयोग को अन्य डेटा संरचना के साथ बदल सकते हैं, हालांकि यह उतना कुशल नहीं हो सकता है।

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

---

[संपादित करें] उदाहरण के बारे में अतिरिक्त विचारों 2

अगर मैं गलत नहीं है, तो पहली बार (Map.!) storage किसी कुंजी के लिए मूल्यांकन करने के लिए मजबूर किया जाता है हूँ, storage संरचना पूरी तरह से बाहर wrung किया जाएगा (लेकिन गणना f दी गई कुंजी के अलावा कुछ भी नहीं होगी)। तो पहला लुकअप एक अतिरिक्त ओ (एन) ऑपरेशन का कारण बनता है, n length domain है। बाद के लुकअप नहीं होंगे, afaik, इस लागत लग रहा है।

विशिष्ट इंट-इंडेक्सेड सूचियों या इंट्रीरी जैसे Lazier संरचनाओं को समान रूप से एक लुकअप के दौरान अपनी संरचना को प्रकट करने की आवश्यकता होती है, लेकिन मानचित्र के विपरीत, उन्हें एक बार में ऐसा करने की आवश्यकता नहीं होती है। अनुक्रमित कुंजी तक पहुंचने तक सूचियां बाहर निकलती हैं। Inttries वांछित कुंजी के केवल "पूर्ण उपसर्ग" (या प्रत्यय? सुनिश्चित नहीं है। किसी भी तरह से लागू किया जा सकता है) पूर्णांक कुंजी बाहर wring। इंडेक्स 11, (1011) 1 (1), 2 (10), 5 (101), और 11 (1011) wring जाएगा। Data.Memocombinators बस सभी चाबियाँ इनट्स (या "बिट्स") में बदल देता है ताकि IntTrie का उपयोग किया जा सके।

पेज। इसके लिए "wring out" से बेहतर वाक्यांश है? शब्द "बल", "रीढ़", और "प्रकट" दिमाग में आते हैं, लेकिन मैं इसके लिए सही शब्द/वाक्यांश के बारे में काफी नहीं सोच सकता।