क्या एड Kmett के प्रत्यावर्तन योजना पैकेज

Question

में फिक्स, म्यू और नू के बीच का अंतर एड Kmett के recursion-scheme पैकेज में तीन घोषणाओं, वहाँ रहे हैं?

Answer 1

Mu एक रिकर्सिव प्रकार को इसके गुना के रूप में दर्शाता है, और Nu इसे इसके सामने प्रकट करता है। हास्केल में, ये आइसोमोर्फिक हैं, और एक ही प्रकार का प्रतिनिधित्व करने के विभिन्न तरीके हैं। यदि आप दिखाते हैं कि हास्केल में मनमाने ढंग से रिकर्सन नहीं है, तो इन प्रकारों के बीच भेद अधिक दिलचस्प हो जाता है: Mu ff का कम से कम (प्रारंभिक) निश्चित बिंदु है, और Nu f इसका सबसे बड़ा (टर्मिनल) निश्चित बिंदु है।

f का एक निश्चित बिंदु एक प्रकार TT और f T के बीच समाकृतिकता है, यानी उलटा कार्यों in :: f T -> T, out :: T -> f T की एक जोड़ी है। प्रकार Fix सीधे आइसोमोर्फिज्म घोषित करने के लिए हास्केल के अंतर्निर्मित प्रकार रिकर्सन का उपयोग करता है। लेकिन आप Mu और Nu दोनों के लिए इन/आउट को कार्यान्वित कर सकते हैं।

एक ठोस उदाहरण के लिए, एक पल का नाटक करें कि आप रिकर्सिव मान नहीं लिख सकते हैं। Mu Maybe के निवासियों, यानी :: forall r. (Maybe r -> r) -> r, प्राकृतिक हैं, {0, 1, 2, ...}; Nu Maybe के निवासियों, यानी :: exists x. (x, x -> Maybe x) मानदंड हैं, 0 0, 1, 2, ..., ∞} हैं। इन प्रकारों के संभावित मूल्यों के बारे में सोचें कि Nu Maybe में एक अतिरिक्त निवासी क्यों है।

आप इन प्रकार के कुछ अंतर्ज्ञान प्राप्त करना चाहते हैं, यह प्रत्यावर्तन के बिना निम्नलिखित लागू करने के लिए (मोटे तौर पर कठिनाई के बढते क्रम में) एक मजेदार व्यायाम किया जा सकता है:

• zeroMu :: Mu Maybe, succMu :: Mu Maybe -> Mu Maybe
• zeroNu :: Nu Maybe, succNu :: Nu Maybe -> Nu Maybe, inftyNu :: Nu Maybe
• muTofix :: Mu f -> Fix f, fixToNu :: Fix f -> Nu f
• inMu :: f (Mu f) -> Mu f, outMu :: Mu f -> f (Mu f)
• inNu :: f (Nu f) -> Nu f, outNu :: Nu f -> f (Nu f)

आप भी इन लागू करने के लिए कोशिश कर सकते हैं, लेकिन वे प्रत्यावर्तन की आवश्यकता होती है:

• nuToFix :: Nu f -> Fix f, fixToMu :: Fix f -> Mu f

Mu f कम से कम तय बिंदु है, और Nu f है सबसे महान, इसलिए एक समारोह लिखना :: Mu f -> Nu f बहुत आसान है, लेकिन एक समारोहलिखनाकठिन है; यह वर्तमान के खिलाफ तैराकी की तरह है।

(पर एक बिंदु मैं इन प्रकार के एक अधिक विस्तृत विवरण लिखने के लिए अर्थ था, लेकिन यह एक छोटे से भी इस प्रारूप के लिए लंबे समय तक हो सकता है।)