क्या हास्केल में साझा करना कभी भी संभव है?

Question

योजना में, आदिम eq? परीक्षण करता है कि क्या इसके तर्क एक ही वस्तु हैं। उदाहरण के लिए, निम्न सूची

(define lst 
    (let (x (list 'a 'b)) 
    (cons x x))) 

में

(eq? (car x) (cdr x)) 

का परिणाम सच है, और इसके अलावा यह सच (car x) और (cdr x) में झाँकने के लिए बिना है। यह आपको उन डेटा संरचनाओं के लिए कुशल समानता परीक्षण लिखने की अनुमति देता है जिनमें बहुत अधिक साझाकरण होता है।

क्या हास्केल में भी वही बात संभव है? उदाहरण के लिए, निम्नलिखित बाइनरी पेड़ कार्यान्वयन

data Tree a = Tip | Bin a (Tree a) (Tree a) 

left (Bin _ l _) = l 
right (Bin _ _ r) = r 

mkTree n :: Int -> Tree Int 
mkTree 0 = Tip 
mkTree n = let t = mkTree (n-1) in Bin n t t 

जो प्रत्येक स्तर पर साझा कर रहा है पर विचार करें। अगर मैं let tree = mkTree 30 के साथ एक पेड़ बना देता हूं और मैं देखना चाहता हूं कि left tree और right tree बराबर हैं, तो मुझे यह पता लगाने के लिए एक बिलियन नोड्स पर जाना होगा कि वे एक ही पेड़ हैं, जो डेटा साझाकरण के कारण स्पष्ट होना चाहिए।

मुझे उम्मीद नहीं है कि हास्केल में डेटा साझा करने का एक आसान तरीका है, लेकिन मुझे आश्चर्य हुआ कि इस तरह के मुद्दों से निपटने के लिए सामान्य दृष्टिकोण क्या हैं, जब दक्षता उद्देश्यों के लिए साझा करना पता लगाना अच्छा होगा (या उदाहरण के लिए चक्रीय डेटा संरचनाओं का पता लगाने के लिए)।

क्या unsafe प्राइमेटिव हैं जो साझाकरण का पता लगा सकते हैं? क्या स्पष्ट पॉइंटर्स के साथ डेटा संरचनाओं का निर्माण करने का एक प्रसिद्ध तरीका है, ताकि आप सूचक समानता की तुलना कर सकें?

Answer 1

बहुत सारे दृष्टिकोण हैं।

1. अद्वितीय आईडी उत्पन्न करें और एक सीमित मानचित्र में सबकुछ चिपकाएं (उदा। IntMap)।
2. अंतिम विकल्प का परिष्कृत संस्करण एक स्पष्ट ग्राफ बनाना है, उदा। fgl का उपयोग कर।
3. stable names का उपयोग करें।
4. IORefs (see also) का उपयोग करें, जिसमें Eq और Ord दोनों शामिल हैं, निहित प्रकार के बावजूद।
5. observable sharing के लिए पुस्तकालय हैं।
6. ऊपर वर्णित अनुसार, reallyUnsafePtrEquality# है लेकिन आपको समझना चाहिए कि इसका उपयोग करने से पहले वास्तव में असुरक्षित क्या है!

this answer about avoiding equality checks altogether भी देखें।

Answer 2

reallyUnsafePtrEquality# है। here

Answer 3

यह भी शुद्ध भाषा हैस्केल में संभव नहीं है।

लेकिन GHC में इसके कार्यान्वयन में, इस तरह के

• ghc-heap-view तरह reallyUnsafePtrEquality# या
• आत्मनिरीक्षण पुस्तकालयों के उपयोग के रूप कमियां, कर रहे हैं।

किसी भी मामले में, नियमित कोड में इसका उपयोग करना बहुत ही असामान्य होगा; अधिकतर मैं कल्पना कर सकता हूं कि किसी चीज़ के लिए एक अत्यधिक विशिष्ट लाइब्रेरी का निर्माण (memoizatoin, हैश टेबल, जो भी हो) जो तब एक सेन, शुद्ध एपीआई प्रदान करता है, स्वीकार्य हो सकता है।