क्या रेंज ट्रैकिंग के दर्द को कम करने के लिए कोई तरीका है?

Question

वर्तमान में एक pull request जोनाथन एस द्वारा नहीं है के साथ एक this README में विस्तार से बताया एडवर्ड Kmett द्वारा एक blog post से विचारों के आधार पर Data.IntMap के कार्यान्वयन को बदलने के लिए।

मूल अवधारणा जोनाथन एस से विकसित है कि एक IntMap एक द्विआधारी पेड़ कि इस तरह दिखता है (मैं स्थिरता की खातिर उनकी विकास के लिए कुछ मामूली परिवर्तन करने के बाद) है:

data IntMap0 a = Empty | NonEmpty (IntMapNE0 a) 
data IntMapNE0 a = 
    Tip !Int a 
    | Bin { lo :: !Int 
     , hi :: !Int 
     , left :: !(IntMapNE0 a) 
     , right :: !(IntMapNE0 a) } 

में इस प्रतिनिधित्व, प्रत्येक नोड एक क्षेत्र कम से कम और सबसे बड़ी कुंजी IntMapNE0 में निहित का संकेत है। थोड़ी सी झुकाव का उपयोग करके इसे पैट्रिकिया ट्राई के रूप में उपयोग करने की अनुमति मिलती है। जोनाथन ने नोट किया कि इस संरचना में लगभग दोगुनी रेंज की जानकारी है जितनी इसकी जरूरत है। बाईं या दाईं रीढ़ के बाद सभी एक ही lo या hi सीमा का उत्पादन करेगा। तो वह उन केवल सहित पूर्वजों द्वारा निर्धारित नहीं बाध्य द्वारा काट:

data IntMap1 a = Empty | NonEmpty { topLo :: !Int, child :: !(IntMapNE1 a) } 
data IntMapNE1 a = 
    Tip a 
    | IntMapNE1 { bound :: !Int 
       , left :: !(IntMapNE1 a) 
       , right :: !(IntMapNE1 a) 

अब प्रत्येक नोड या तो एक बाईं बाध्य या बाध्य एक सही, लेकिन दोनों नहीं है। एक सही बच्चे के पास केवल बाएं बाएं होंगे, जबकि बाएं बच्चे के पास केवल सही बाध्य होगा।

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

data L 
data R 
newtype IntMap a = IntMap (IntMap_ L a) deriving (Eq) 
data IntMap_ t a = NonEmpty !Int a !(Node t a) | Empty deriving (Eq) 
data Node t a = Bin !Int a !(Node L a) !(Node R a) | Tip deriving (Eq, Show) 

इस नए कार्यान्वयन के कुछ पहलू काफी आकर्षक हैं। सबसे महत्वपूर्ण बात यह है कि सबसे अधिक इस्तेमाल किए जाने वाले परिचालन काफी तेजी से होते हैं। कम महत्वपूर्ण बात, लेकिन बहुत अच्छी तरह से, थोड़ा सा झुकाव समझना बहुत आसान है। लापता रेंज जानकारी पेड़ के माध्यम से नीचे गुजर:

हालांकि, वहाँ एक गंभीर दर्द बिंदु है। इस खोज के, सम्मिलन, आदि के लिए इतना बुरा नहीं है, लेकिन संघ और चौराहे कोड में बहुत गंभीरता से बालों हो जाता है। क्या कोई अमूर्त है जो इसे स्वचालित रूप से करने की अनुमति देगा?

एक जोड़े को अत्यंत अस्पष्ट विचार:

1. प्रेत प्रकार उपचार टाई के लिए एक कस्टम वर्ग के साथ इस्तेमाल किया जा सकता है सीधे मनमानी के लिए?

2. "गायब टुकड़ा" प्रकृति कुछ जिपर परिस्थितियों की याद दिलाता है। क्या उस क्षेत्र से विचारों का उपयोग करने का कोई तरीका हो सकता है?

---

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

Answer 1

क्या कोई अमूर्तता है जो इसे स्वचालित रूप से करने की अनुमति देगी?

आपको पैटर्न समानार्थी शब्दों का एक सेट परिभाषित करने में सक्षम होना चाहिए जो आपको देते हैं। मैं आपके कोड के दूसरे से अंतिम संस्करण से शुरू करूंगा, यानी।:

data IntMap1 a = Empty | NonEmpty { topLo :: !Int, child :: !(IntMapNE1 a) } 
data IntMapNE1 a = 
    Tip a 
    | IntMapNE1 { bound :: !Int 
       , left :: !(IntMapNE1 a) 
       , right :: !(IntMapNE1 a) 

हम एक Either में माता पिता से बाध्य के साथ इस तरह के एक मूल्य टपल (यह दर्शाता है कि क्या यह एक कम या एक उच्च बाध्य है)।

viewLoHi (Left lo, IntMapNE1 hi left right) 
    = Just (lo, hi, (Left lo, left), (Right hi, right) 
viewLoHi (Right hi, IntMapNE1 lo left right) 
    = Just (lo, hi, (Left lo, left), (Right hi, right) 
viewLoHi _ 
    = Nothing 

pattern Bin' lo hi left right <- (viewLoHi -> Just (lo, hi, left, right)) 

शीर्ष स्तर के डेटा प्रकार अलग है, तो इसका इस्तेमाल करते हुए केवल NonEmpty' और Bin' के रूप में आप पेड़ पार अपने स्वयं के पैटर्न पर्याय

viewLoHi' (NonEmpty lo child) = viewLoHi (Left lo, child) 
viewLoHi' Empty = Nothing 

pattern NonEmpty' lo hi left right <- (viewLoHi' -> Just (lo, hi, left, right) 

की जरूरत है, बहीखाता अब पूरी तरह से छिपा होना चाहिए। (कोड का परीक्षण नहीं किया गया है, इसलिए यहां टाइपो होंगे)