हस्केल - असंभव संभव है?

यह ज्ञात है कि कुछ कार्य Integer -> Bool सही है या नहीं यह निर्धारित करने का कार्य कम्प्यूटेशनल रूप से कम से कम संख्या के लिए अघुलनशील है। हालाँकि, पहली नज़र में कुछ ऐसा प्रतीत होता है, जैसे (Integer -> Bool) -> Maybe Integer इस लेख में (यथा (Integer -> Bool) -> Maybe Integer समारोह (Integer -> Bool) -> Maybe Integer ) वर्णित किया जाएगा।

शुरू करने के लिए, हम अपने प्रकार की प्राकृतिक संख्याएँ निर्धारित करेंगे, लगभग शाब्दिक रूप से उनकी सामान्य गणितीय परिभाषा (भविष्य में इसकी आवश्यकता क्यों होगी):

 data Nat = Zero | Succ Nat deriving (Eq, Ord, Show) 

दूसरे शब्दों में, एक धनात्मक पूर्णांक या तो शून्य होता है या कुछ सकारात्मक पूर्णांक एक (उत्तराधिकारी से प्राप्त) द्वारा बढ़ाया जाता है।

इसके अलावा, सुविधा के लिए, हम इस प्रतिनिधित्व में संख्याओं पर मूल संचालन (जोड़, गुणा, Integer से रूपांतरण) को परिभाषित करते हैं:

 instance Num Nat where Zero + y = y Succ x + y = Succ (x + y) Zero * y = Zero Succ x * y = y + (x * y) fromInteger 0 = Zero fromInteger n = Succ (fromInteger (n-1)) 

अब तक, ऐसा लगता है, नियमित Integer से इस प्रकार के मतभेदों के संदर्भ में कुछ खास नहीं है।

याद रखें कि हम प्रपत्र का एक फ़ंक्शन चाहते हैं (Nat -> Bool) -> Maybe Nat , जिसके परिणामस्वरूप एक संख्या होगी जिस पर इनपुट फ़ंक्शन True , या ऐसा कोई नंबर नहीं होने पर Nothing नहीं। एक पहला सन्निकटन हो सकता है, उदाहरण के लिए, एक समान कार्य:

 lyingSearch :: (Nat -> Bool) -> Nat lyingSearch f | f Zero = Zero | otherwise = Succ (lyingSearch (f . Succ)) 

वास्तव में, यह लगभग स्पष्ट है कि यदि वांछित संख्या मौजूद है, तो यह फ़ंक्शन सही उत्तर देगा। वास्तव में, यदि f Zero == True , तो वापसी मूल्य Zero - सत्य होगा। अन्यथा, फ़ंक्शन x+1 लौटाएगा, जहां x वह मान है जिस पर फ़ंक्शन f(x+1) सत्य है - भी सत्य है।
हालांकि, इस फ़ंक्शन का एक lyingSearch : मामले में जब कोई आवश्यक संख्या नहीं होती है, तो फ़ंक्शन हर चरण पर पुनरावृत्ति पर जाएगा और वापस आ जाएगा, वास्तव में, अनंत: Succ (Succ (Succ (... , जहां घोंसला कभी खत्म नहीं होगा। Haskell आलस्य के कारण, यह एक सामान्य स्थिति है, लेकिन अनंत वांछित जवाब नहीं है - इसलिए, इस मामले में, फ़ंक्शन "झूठ" होगा।

दिलचस्प है, उपरोक्त lyingSearch फ़ंक्शन के आधार पर एक पूरी तरह से काम करने वाला समाधान बनाया जा सकता है। search फ़ंक्शन को निम्नानुसार परिभाषित search :

 search f | f possibleMatch = Just possibleMatch | otherwise = Nothing where possibleMatch = lyingSearch f 

पहली नज़र में, यह स्पष्ट नहीं है कि यह कैसे काम करेगा, और क्या यह होगा। आइए सरल उदाहरणों के साथ देखें:

 ghci> search (\x -> x*x == 16) --     lyingSearch Just (Succ (Succ (Succ (Succ Zero)))) ghci> search (\x -> x*x == 15) Nothing 

यही है, search फ़ंक्शन ने सही ढंग से निर्धारित किया कि पंद्रह के बराबर वर्ग के साथ कोई प्राकृतिक संख्या नहीं है।

वास्तव में, यदि आप देखते हैं, तो सब कुछ सरल है। lyingSearch से संभावित परिणाम प्राप्त lyingSearch (जो कि हमेशा Nat का एक मान्य मूल्य है), हम बस इसे f के इनपुट पर फ़ीड करते हैं और रिटर्न मान की जांच करते हैं। यदि वांछित संख्या मौजूद है, तो (जैसा कि पहले ही समझाया जा चुका है) possibleMatch है, केवल वह संख्या है, और इसलिए चेक सफल होगा। अन्यथा, क्योंकि f किसी भी इनपुट मूल्य के लिए समाप्त हो जाता है, हम False और Nothing लौटाते हैं।

search फ़ंक्शन वास्तव में किसी भी विधेय ( Nat->Bool फ़ंक्शन) के लिए काम करता है, और एक निश्चित समय में समाप्त होता है (निश्चित रूप से, बशर्ते कि किसी भी प्रकार के Nat लिए भी समाप्त हो जाए)। हालांकि, पारित किसी भी तर्क के लिए समाप्ति की स्थिति f बहुत मजबूत है, और यह है कि यह दृढ़ता से अनुमेय विधेयकों के सेट को सीमित करता है: उदाहरण के लिए, fx = x*x + 1 == x एक अनंत लूप होगा। ऐसा लगता है कि यह ऐसा नहीं है, क्योंकि किसी भी संख्या के लिए ऐसा फ़ंक्शन समाप्त होता है? यह पता चला है कि पहले से ही उल्लेख किए गए निरर्थकता के अलावा किसी और के लिए: समान चिह्न के बाईं और दाईं ओर असीम रूप से Succ (Succ (Succ (... , और तदनुसार यह निर्धारित करना संभव नहीं होगा कि बाएं और दाएं पक्ष समान हैं। इस कारण से, इस फ़ंक्शन के लिए इस फ़ंक्शन का उपयोग करना असंभव है। Integer लिए एक समान प्रकार का निर्माण।

अब आप सरल शब्दों में समझा सकते हैं कि हमेशा-समाप्त होने वाले कार्यों के लिए सब कुछ क्यों और कैसे काम करता है। आखिरकार, यदि f ने अनंत को समाप्त कर दिया, तो वह अनुक्रम Succ (Succ (Succ (... , तो किसी भी स्थिति में यह Succ कंस्ट्रक्टर्स की निश्चित संख्या से अधिक नहीं (खुलता है) का उपयोग करता है।

अनिवार्य रूप से उसी तरह, आप अन्य प्रकारों के लिए search जैसे कार्य बना सकते हैं। सापेक्ष रूप से सरल उदाहरण भी वास्तविक संख्याएं हैं, प्रत्येक को संख्याओं की अंतहीन सूची के रूप में दर्शाया गया है (देखें सीमलेस इम्पॉसिबल फंक्शनल प्रोग्राम्स )। हैकेज पर एक सामान्य पैकेज अनंत-खोज है , जो उचित मोनाड और संबंधित कार्यों को प्रदान करता है।

पुनश्च: यह लेख खोजा जा सकने वाले डेटा प्रकारों के "रिटेलिंग" द्वारा थोड़ा पूरक है, इसलिए इसे अनुवाद के रूप में चिह्नित नहीं किया गया है।