दोगुनी लिंक्ड सूचियों को कैसे कार्यान्वित करें

Question

क्या हैस्केल में दोगुनी जुड़ी सूची होना संभव है, और उन्हें लागू करने का आदर्श समाधान क्या है? मैं एक दृश्य ग्राफ को कार्यान्वित कर रहा हूं जहां प्रत्येक विजेट में माता-पिता के साथ-साथ एक बच्चा होता है, और ग्राफ को ऊपर और नीचे देखने के लिए फायदेमंद होता है।

Answer 1

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

उदाहरण के लिए, कल्पना करें कि आपके पास एक सूची [1, 2, 3, 4, 5] है जिसे आप दोगुना लिंक करना चाहते हैं।

data DoubleList a 
    = LeftEnd a (DoubleList a) 
    | Middle a (DoubleList a) (DoubleList a) 
    | RightEnd a (DoubleList a) 

(मैं सादगी के लिए दोनों सिरों के लिए दो अलग-अलग निर्माताओं का उपयोग करें) ऊपर सूची का निर्माण करने के लिए, आप पहली बार पहला तत्व का निर्माण करने के लिए है: अब, चलो कैसे सूची प्रतिनिधित्व किया है की कल्पना करते हैं

let e1 = LeftEnd 1 e2 
    e2 = Middle 2 e1 ... 

:

let e1 = LeftEnd 1 ... 

लेकिन पहले तत्व के निर्माण के लिए, आप पहले से ही दूसरा तत्व की आवश्यकता है

और दूसरा तत्व के लिए, आप की जरूरत तीसरे, आदि:

let e1 = LeftEnd 1 e2 
    e2 = Middle 2 e1 e3 
    e3 = Middle 3 e2 e4 
    e4 = Middle 4 e3 e5 
    e5 = RightEnd 5 e4 

यह आलसी मूल्यांकन की वजह से हास्केल में ऐसा करना संभव है, इस रणनीति को "गाँठ बांधना" कहा जाता है (और आपको सचमुच इसे let ब्लॉक में डालना नहीं है; आप निर्माण को कार्यों में विभाजित कर सकते हैं)

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

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

अन्यथा, आप केवल ज़िप्पर का उपयोग करना चाहते हैं, लेकिन सूचियों के बजाय पेड़ के लिए उनका उपयोग करें। ज़िप्पर के बारे में अधिक जानकारी Haskell Wiki पर मिल सकती है। ज़िप्पर इस स्थिति में बहुत अच्छी तरह से फिट होंगे, क्योंकि वे आपके द्वारा की जाने वाली सटीक कार्यक्षमता प्रदान करते हैं: यदि आप जिपर के साथ एक पेड़ पर जाते हैं, तो आप जिस पेड़ के दौरे पर जा रहे हैं उसके हिस्से के "माता-पिता" तक पहुंच प्राप्त करते हैं, लेकिन पेड़ में माता-पिता के संदर्भ शामिल नहीं हैं।

Answer 2

चूंकि आप (आमतौर पर) हास्केल में ओओ-स्टाइल ऑब्जेक्ट्स नहीं रखते हैं, इसलिए यह डेटा अजीब होने के बारे में सोचने के लिए अजीब है। यह ध्यान रखना महत्वपूर्ण है कि आप आमतौर पर हास्केल डेटा प्रकारों में एकत्रीकरण का उपयोग नहीं करते हैं, इसके बजाय संरचना का पक्ष लेते हैं।

आप यह देखने के लिए XMonad पर देखना चाहते हैं कि उनका डिज़ाइन आपकी आवश्यकताओं से मेल खाता है (कोड आश्चर्यजनक रूप से पठनीय है)।

आप भी अपने डिज़ाइन को पुन: स्थापित करना चाहते हैं ताकि आपको कभी भी ऊपर देखने की आवश्यकता न हो (उदाहरण के लिए, बच्चों को "कॉलबैक" पास करके)।

आप यह भी देखना चाहेंगे कि आप अपने पूरे ग्राफ के लिए जिपर लिख सकते हैं या नहीं।