क्यों अपरिवर्तनीय डेटाटाइप प्रकारों को प्रतिबंधित करते हैं जैसे 'डेटा खराब ए = सी (खराब ए -> ए)' जहां टाइप रिकर्सन के सामने होता है ->?

Question

AGDA Inductive Data Types and Pattern Matching राज्यों पर मैनुअल:

सामान्य सुनिश्चित करने के लिए आगमनात्मक घटनाओं सख्ती से सकारात्मक स्थानों पर दिखाई देने चाहिए। उदाहरण के लिए, निम्नलिखित डेटाप्रकार अनुमति नहीं है:

data Bad : Set where 
    bad : (Bad → Bad) → Bad 

के बाद से वहाँ निर्माता के लिए बहस में बुरा की नकारात्मक घटना है।

यह आवश्यकता अनिवार्य डेटा प्रकारों के लिए क्यों आवश्यक है?

Answer 1

डेटा प्रकार आपके द्वारा दिया गया विशेष है कि यह untyped लैम्ब्डा पथरी का एक एम्बेडिंग है।

data Bad : Set where 
    bad : (Bad → Bad) → Bad 

unbad : Bad → (Bad → Bad) 
unbad (bad f) = f 

चलो देखते हैं कि कैसे। (AGDA में हालांकि नहीं)

e := x | \x. e | e e' 

हम प्रकार Bad की AGDA शर्तों के untyped लैम्ब्डा पथरी शब्दों से कोई अनुवाद [[e]] परिभाषित कर सकते हैं: याद है, untyped लैम्ब्डा पथरी इन शर्तों है

[[x]]  = x 
[[\x. e]] = bad (\x -> [[e]]) 
[[e e']] = unbad [[e]] [[e']] 

अब आप Bad प्रकार की गैर-टर्मिनेशन अवधि का उत्पादन करने के लिए अपने पसंदीदा गैर-टर्मिनिंग untyped लैम्ब्डा शब्द का उपयोग कर सकते हैं। उदाहरण के लिए, हम नीचे प्रकार Bad के गैर समाप्त अभिव्यक्ति को (\x. x x) (\x. x x) उसका अनुवाद कर सकें:

unbad (bad (\x -> unbad x x)) (bad (\x -> unbad x x)) 

हालांकि प्रकार इस तर्क के लिए एक विशेष रूप से सुविधाजनक रूप हुआ, यह किसी भी करने के लिए काम का एक सा के साथ सामान्यीकृत किया जा सकता रिकर्सन की नकारात्मक घटनाओं के साथ डेटा प्रकार।

Answer 2

एक उदाहरण यह है कि कैसे एक डेटा प्रकार हमें किसी भी प्रकार में रहने की अनुमति देता है टर्नर, डीए में दिया जाता है। (2004-07-28), Total Functional Programming, संप्रदाय। 3.1, पेज में 758 नियम 2: प्रकार प्रत्यावर्तन covariant होना चाहिए "

---

के एक अधिक विस्तृत उदाहरण हास्केल का उपयोग कर करते हैं हम एक साथ शुरू करेंगे।" बुरा "पुनरावर्ती डेटा प्रकार

data Bad a = C (Bad a -> a) 

।

और प्रत्यावर्तन के किसी अन्य रूप के बिना इसे से Y combinator निर्माण करते हैं। इसका मतलब है कि इस तरह के एक डेटा प्रकार के होने प्रत्यावर्तन के किसी भी प्रकार का निर्माण, या एक अनंत प्रत्यावर्तन द्वारा किसी भी प्रकार में निवास करने के लिए हमें अनुमति देता है।

,210

untyped लैम्ब्डा पथरी म Y Combinator यह के लिए महत्वपूर्ण है कि हम x x में खुद को x लागू के रूप में

Y = λf.(λx.f (x x)) (λx.f (x x)) 

परिभाषित किया गया है। टाइप की गई भाषाओं में यह सीधे संभव नहीं है, क्योंकि कोई वैध प्रकार x संभवतः संभवतः नहीं हो सकता है। लेकिन हमारे Bad डेटा प्रकार इस सापेक्ष जोड़ने/निर्माता को दूर करने की अनुमति देता है:

selfApp :: Bad a -> a 
selfApp (x@(C x')) = x' x 

x :: Bad a ले जाने पर हम अपने निर्माता खोलने और खुद x को समारोह के अंदर लागू कर सकते हैं। एक बार जब हम ऐसा करने के तरीके पता है, यह Y Combinator निर्माण करने के लिए आसान है:

yc :: (a -> a) -> a 
yc f = let fxx = C (\x -> f (selfApp x)) -- this is the λx.f (x x) part of Y 
     in selfApp fxx 

ध्यान दें कि न selfApp और न ही yc पुनरावर्ती हैं, वहाँ अपने आप को एक समारोह का कोई पुनरावर्ती कॉल है। रिकर्सन केवल हमारे रिकर्सिव डेटा प्रकार में दिखाई देता है।

हम जांच सकते हैं कि निर्मित संयोजक वास्तव में ऐसा करता है जो इसे करना चाहिए। हम एक अनंत लूप बना सकते हैं:

loop :: a 
loop = yc id 

या गणना मान लीजिए कि GCD करते हैं:

gcd' :: Int -> Int -> Int 
gcd' = yc gcd0 
    where 
    gcd0 :: (Int -> Int -> Int) -> (Int -> Int -> Int) 
    gcd0 rec a b | c == 0  = b 
        | otherwise = rec b c 
     where c = a `mod` b