हास्केल: आम Corecursive भ्रम

Question

तो मैं एक ग्राफ दूरी एल्गोरिथ्म के बारे में आज रात में सोच रहा था, और इस के साथ आया था, जबकि मैं कार में गाड़ी चला रहा था:

module GraphDistance where 
import Data.Map 

distance :: (Ord a) => a -> Map a [a] -> Map a Int 
distance a m = m' 
    where m' = mapWithKey d m 
     d a' as = if a == a' then 0 else 1 + minimum (Prelude.map (m'!) as) 

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

मैं अपने आप को समझाने के लिए यह कोड करने के लिए ऊपर था:

ghci> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])] 
fromList [(0,1),(1,0),(2,^CInterrupted. 

लेकिन अब मुझे लगता है कि मैं बहुत ज्यादा यह सोचा है के माध्यम से।

क्या सामान्य त्रुटियों और एंटी-पैटर्न की एक सूची है जो कोरक्रर्सिव डेटा से निपटने पर है, जिसे मैं पर पढ़ सकता हूं, इसलिए मैं अपने दिमाग को कोरकर्सिवली सोचने के लिए प्रशिक्षित कर सकता हूं? अनुभव ने मुझे गैर-कोरकर्सिव डेटा के माध्यम से सोचने के लिए काफी अच्छी तरह से प्रशिक्षित किया है, लेकिन अगर मैं कर सकता हूं तो मैं दूसरों की गलतियों से सीखना चाहता हूं।

Answer 1

ठीक है, कोरकर्सिव डेटा से निपटने के दौरान वास्तव में केवल एक मौलिक गलती है, और यह लापरवाही से रिकर्सन का उपयोग कर है!

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

मुद्दे पर प्रत्यावर्तन, तो, (+) और minimum के संयोजन की वजह से हो रहा है: जब न्यूनतम खोजने, 1 हमेशा 1 + n की तुलना में कम है, क्या n है के बारे में चिंता की जरूरत के बिना हो जाएगा ... लेकिन वहाँ कोई रास्ता नहीं है पूरे मूल्य की गणना किए बिना Int एस की तुलना करने के लिए।

संक्षेप में, एल्गोरिदम तुलना करने में सक्षम होने की अपेक्षा करता है कि को केवल 0 पर लागू किया गया था; यह कहना है, यह आलसी प्राकृतिक संख्याओं को "शून्य" और "उत्तराधिकारी" का उपयोग करके परिभाषित करना चाहता है।

देखो:

data Nat = Z | S Nat 

natToInt :: Nat -> Int 
natToInt Z = 0 
natToInt (S n) = 1 + natToInt n 

instance Show Nat where show = show . natToInt 

instance Eq Nat where 
    Z == Z = True 
    (S n1) == (S n2) = n1 == n2 
    _ == _ = False 

    Z /= Z = False 
    (S n1) /= (S n2) = n1 /= n2 
    _ /= _ = True 


instance Ord Nat where 
    compare Z Z = EQ 
    compare Z (S _) = LT 
    compare (S _) Z = GT 
    compare (S n1) (S n2) = compare n1 n2 

और फिर GHCi में:

> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])] 
fromList [(0,1),(1,0),(2,1),(3,2)] 

सबूत है कि अपने एल्गोरिथ्म काम करता है ^[0]; इसका कार्यान्वयन सिर्फ गलत था।

---

अब, एक मामूली बदलाव के रूप में, के लिए एक अलग ग्राफ करने के लिए अपने एल्गोरिथ्म लागू करें:

> distance 1 $ fromList [(0,[1]),(1,[0]),(2,[3]),(3,[2])] 

... क्या हम यह करने के लिए उम्मीद करते हैं? नोड्स 2 या 3 के लिए नोड 1 से दूरी क्या है?

fromList [(0,1),(1,0),(2,^CInterrupted. 

फिर भी, एल्गोरिथ्म इस ग्राफ पर सही ढंग से काम करता है:

GHCi में यह चल रहा है स्पष्ट परिणाम है। क्या आप समस्या देख सकते हैं? यह जीएचसीआई में क्यों लटका हुआ?

• लेज़ी, संभवतः अनंत डेटा, corecursively
• परिमित डेटा उत्पन्न, रिकर्सिवली भस्म
:

---

सारांश में, आप स्पष्ट रूप से दो रूपों है कि स्वतंत्र रूप से नहीं मिलाया जा सकता के बीच अंतर करने की जरूरत है

दोनों रूपों को संरचना-अज्ञेय तरीके से परिवर्तित किया जा सकता है (उदाहरण के लिए, map दोनों सीमित और अनंत सूचियों पर काम करता है)। कोडाटा को कोरकर्सिव एल्गोरिदम द्वारा संचालित, वृद्धिशील रूप से उपभोग किया जा सकता है; डेटा को रिकर्सिवली एल्गोरिदम द्वारा सीमित रूप से उत्पन्न किया जा सकता है।

आप ऐसा नहीं कर सकते हैं क्या उपभोग codata रिकर्सिवली (जैसे, एक अनंत सूची तह बाएं) या corecursively डेटा उत्पन्न (हास्केल में दुर्लभ है, आलस्य के कारण) है।

[0]: असल में, यह कुछ इनपुट (जैसे, कुछ डिस्कनेक्ट किए गए ग्राफ) पर असफल हो जाएगा, लेकिन यह एक अलग मुद्दा है।