Löb और möb: हास्केल में अजीब लूप

यह लेख का एक काफी मुफ्त अनुवाद है। तथ्य यह है कि एक पंक्ति में निर्माण के बावजूद, सामग्री को समझना मुश्किल है।
इस बात को ध्यान में रखते हुए कि प्रील्यू की टिप्पणियों में या हास्केल को कैसे प्यार किया जाए उन्होंने पूछा कि कोड स्पष्ट हो, मैंने पर्याप्त टिप्पणी की, और मुझे उम्मीद है कि कोड उन लोगों के लिए स्पष्ट होगा जो हास्केल से दूर हैं।

चलिए सबसे मुश्किल से शुरू करते हैं - शीर्षासन के साथ: बहुतों को उसकी सारी बातें समझ नहीं आती हैं।
हास्केल एक साफ और आलसी कार्यात्मक भाषा है।
लोएब एक जर्मन गणितज्ञ है, जिसके बारे में हम थोड़ी देर बाद बात करेंगे।
खैर, और अंत में, सबसे दिलचस्प बात अजीब छोरों है।

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

अजीब छोरों ने अपनी सुंदरता से लोगों को उत्साहित किया। और यह बहुत अच्छा है जब आप उन्हें सबसे अप्रत्याशित स्थानों में पाते हैं। हास्केल में अजीब छोरों के साथ बहुत दिलचस्प कार्य लिखे जा सकते हैं।

जर्मन गणितज्ञ लोएब बीसवीं शताब्दी के 39 वें वर्ष में यूके चले गए। लोएब, विशेष रूप से, विकसित गणितीय तर्क और दुनिया मुख्य रूप से लोएब के प्रमेय के लिए जाना जाता है। इस प्रमेय ने गणित के अधूरेपन पर गोडेल की रचनाओं को विकसित किया। एक बयान की उकसावे और बयान के बीच संबंधों पर लोएब का प्रमेय, यह बताता है कि

किसी भी सिद्धांत में पीनो की स्वयंसिद्धता (प्राकृतिक संख्याओं के बारे में स्वयंसिद्धता) शामिल हैं, किसी भी कथन के लिए P का कथन "यदि P प्रमाणित है, तो P सत्य है" तभी संभव है जब कथन P स्वयं सिद्ध हो।

कथन की यह सारी जटिलता प्रतीकात्मक रूप से लिखी जा सकती है:


क्या हास्केल में इस तरह के समारोह को लिखना संभव है? आप कर सकते हैं! और सिर्फ एक लाइन!

लोएब

loeb हास्केल पर उन विशेषताओं में से एक है जो एक ही समय में आकर्षक, पागल, सरल और जटिल दिखते हैं।

1. फ़ंक्शन लिखना बहुत आसान है
2. कार्य को समझना कठिन है
3. फ़ंक्शन का उपयोग करना आसान है
4. फंक्शन एक्सप्लोसिव है

कार्यान्वयन

स्मार्ट लग रहा है? आइए इसे बदलते हैं, आपको loeb फ़ंक्शन loeb करते हैं:

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x 

सभी सुंदरता महसूस करो! फिर अगले अनुभाग पर जाएं।
नहीं? हम्म ... शायद आप हास्केल को अच्छी तरह से नहीं जानते हैं? फिर मैं और अधिक विस्तार से बताऊंगा।
कुछ चतुर लोग पूछेंगे कि दो लाइनें क्यों हैं, और एक नहीं, और वे सही होंगे। लेकिन केवल आंशिक रूप से। तथ्य यह है कि पहली पंक्ति एक हस्ताक्षर है: एक घोषणा, किस प्रकार के साथ, फ़ंक्शन कितने मापदंडों के साथ काम करता है। हालाँकि, यह लाइन वैकल्पिक है - यदि आप इसे नहीं लिखते हैं, तो दुभाषिया (और संकलक) स्वयं प्रकारों को प्राप्त करेगा:

 loeb :: Functor f => f (fa -> a) -> fa 

हस्ताक्षर को तीन भागों में विभाजित किया जाता है - पहले हम फ़ंक्शन का नाम लिखते हैं, फिर हम कहते हैं कि हम प्रकार की घोषणा करना चाहते हैं, :: , फिर बोल्ड एरो ( => ) के लिए हम मापदंडों पर प्रतिबंध लिखते हैं - मैं कुछ मामलों में नीचे तक समझाऊंगा। और अंत में - वास्तव में, प्रकार:
f (fa -> a) -> fa , देखें कि Loeb की प्रमेय के लिए रिकॉर्ड कितना करीब है: - हाँ, एक से एक!
मैं ध्यान देता हूं कि पुस्तकालय कार्यों का उपयोग किए बिना फ़ंक्शन लिखा गया था!

यह समझाने से पहले कि हस्ताक्षर का क्या अर्थ है, जब तक हम स्वयं फ़ंक्शन के माध्यम से जाते हैं, चलो उस पर समय बर्बाद न करें और फ़ंक्शन को 3 लाइनों में लिखें, जैसा कि कोई भी सभ्य हास्केलिस्ट करेगा:

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x 

यहां यह स्पष्ट है कि वह शब्द where एक सेवा शब्द है और आंतरिक कार्य को परिभाषित करना संभव बनाता है।

कैसे पढ़ें? ... अरे हाँ, मुझे कहना होगा कि हास्केल में कोई अतिरिक्त कोष्ठक नहीं हैं, और जहां अधिकांश भाषाएं लिखेंगे
f (x, y, z) = ... , हास्केल में वे केवल fxyz = ...

यह कोड से देखा जा सकता है कि loeb फ़ंक्शन एक तर्क का एक फ़ंक्शन है और इसे go फ़ंक्शन के माध्यम से निर्धारित किया go है।

फंक्शन फ़ंक्शन को fmap और fmap फ़ंक्शन के माध्यम से परिभाषित किया गया है। fmap फ़ंक्शन स्वयं सूचियों के लिए map फ़ंक्शन का एक सामान्यीकरण है और इसे निम्नानुसार परिभाषित किया गया है:

 class Functor f where fmap :: (a -> b) -> fa -> fb 

यह सिर्फ एक घोषणा है। ओओपी कक्षाएं किसी भी प्रकार से संबंधित नहीं हैं। हमारे मामले में, हमें वास्तव में पहली पंक्ति को समझने की आवश्यकता नहीं है, यह सिर्फ यह कहता है कि f , fmap समारोह में बहुरूपी होगा।
तो, आइए हस्ताक्षर को ध्यान से देखें कि इसका क्या मतलब है।
यह कहा जाता है कि fmap फंक्शन दो तर्कों का एक फंक्शन है - (a -> b) और fa , आउटपुट fb ।
यह समझना आसान है कि (a -> b) एकल तर्क का एक कार्य है जो कुछ इनपुट लेता है (हम आमतौर पर इस प्रकार को कॉल करेंगे, यह कोई भी हो सकता है - उदाहरण के लिए, एक स्ट्रिंग, संख्या या फ़ाइल) और आउटपुट भी या प्रकार (हम इसे b द्वारा निरूपित करते हैं, यह याद रखना कि b विशेष रूप से हो सकता a )।
fa - a आधार पर कुछ जटिल मूल्य के रूप में समझा जा सकता है और अगर हम f(a) रूप में पढ़ते हैं, तो यह समझना आसान होगा
यदि आप गणित में एक फ़नकार की परिभाषा खोलते हैं, तो आप एक अद्भुत समानता देखेंगे।
यही है, अगर हम पूरी समझ से विचलित होते हैं और सहज ज्ञान की ओर मुड़ते हैं, तो यह स्पष्ट है कि fmap फ़ंक्शन फ़ंक्शन को f माध्यम से मान पर लागू करता है, और, एक नियम के रूप में, यह मामला है।

अपनी आवश्यकताओं के लिए, हमें पूरी तरह से फंक्शनलर्स की पूरी शक्ति को समझने की आवश्यकता नहीं है, आइए सूचियों को देखें:

 instance Functor [] where fmap = map 

यह यहां आसान हो गया - सूचियों के लिए, fmap फ़ंक्शन पूरी तरह से map फ़ंक्शन के समान है। खैर, सभी map पहले से ही map फ़ंक्शन को जानते हैं, यह सूची के सभी सदस्यों के लिए फ़ंक्शन का अनुप्रयोग है। हास्केल में, इसे बहुत सरलता से परिभाषित किया गया है:

 map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = fx : map f xs 

हम हस्ताक्षर को देखते हैं: सब कुछ पहले से ही यहां परिचित है - दो तर्कों का एक फ़ंक्शन - एक पैरामीटर का एक फ़ंक्शन और एक सूची। नतीजतन, हमें एक संशोधित सूची मिलती है।
दूसरी पंक्ति कहती है कि खाली सूची के लिए, फ़ंक्शन की परवाह किए बिना ("_" - हम कहते हैं कि हमें इसके मूल्य को जानने की आवश्यकता नहीं है) एक खाली सूची होगी।
अन्य मामलों के लिए, हम सूची को सिर और बाकी हिस्सों में विभाजित कर सकते हैं ( x : xs , अक्षर s ध्यान दें, अंग्रेजी में इसका अर्थ है बहुवचन, माना जाता है कि xs में बहुत से xs ) और दूसरी सूची लौटाते हैं, जहां सिर के लिए हम फ़ंक्शन लागू करते हैं, और पूंछ, हम अपने वर्णित फ़ंक्शन को पुन: लागू करते हैं।



ठीक है, चलो फिर से हमारी परिभाषा पर चलते हैं:

 go = fmap ($ go) x 

डॉलर के साथ क्या कार्य है? क्या यह अंकल सैम के बिना संभव है? खैर, आप, यह शुद्ध भाषा है! $ एक साधारण ऑपरेटर फ़ंक्शन है, जिसे एक एपेक्टिव फ़ंक्शन कहा जाता है और इसे प्राथमिक रूप से परिभाषित किया जाता है:

 ($) :: (a -> b) -> a -> b f $ x = fx 

नहीं, यह आपको प्रतीत नहीं होता है, अनुप्रयोग कार्य कुछ भी नहीं करता है, लेकिन अक्सर इसका उपयोग कोष्ठक के बजाय किया जाता है।

ठीक है, इसलिए आपको भ्रमित करने के लिए नहीं, हम loeb अभिव्यक्तियों का उपयोग करके loeb फ़ंक्शन को फिर से loeb :

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap (\z -> z go) x 

लैम्ब्डा एक्सप्रेशन पढ़ना आसान है: \z -> z go अर्थ है कि लैम्बडा फंक्शन (स्लैश ग्रीक वेरिएबल लैम्ब्डा - λ से मिलता-जुलता है) एक वेरिएबल z , वेल और एरो -> रूप में पढ़ा जाता है =

महान, हम पढ़ने में सक्षम थे! अब इसे समझना बाकी है!

loeb क्या करता है?

लघु संस्करण: loeb परिणाम को खुद के संदर्भ में गणना करता है, लेकिन जब आप पहली बार पुनरावृत्ति के बारे में सुनते हैं, तो यह उस समय की तुलना में पागलपन है।

विस्तृत संस्करण: loeb उपयोग loeb करें? यह कहाँ उपयोगी है? उदाहरण के लिए, आप सूची फ़ंक्शंस के लिए एक स्प्रेडशीट (जैसे एक्सेल) बना सकते हैं - []:

 xs :: [a] xs = [...] fs :: [[a] -> a] fs = [...] rs :: [a] rs = [ f xs | f <- fs ] -- r = f xs 

मान लीजिए हमारे पास एक सूची है xs :: [a] । और हमारे पास कार्यों की एक सूची है जो मूल्यों को सूचीबद्ध करती है, fs :: [[a] -> a] । हम सूची से प्रत्येक फ़ंक्शन के लिए लेते हैं और हम तत्वों की सूची पर लागू होते हैं, इस प्रकार r का एक नया मूल्य प्राप्त करते हैं। हम सूची rs में सभी r एकत्र करते हैं।

 [ f xs | f <- fs ] 

यह समझना मुश्किल है, लेकिन फिर भी - सूची के प्रत्येक सेल में हम मानों की सूची में एक फ़ंक्शन (सूची से) लागू करते हैं, इसे दाईं से बाईं ओर पढ़ा जाता है।

इन क्रियाओं के आधार पर, हमने xs मानों की सूची और fs फ़ंक्शंस की सूची से rs गणना की।

और अब सबसे महत्वपूर्ण बात - आप xs मूल्यों की सूची नहीं ले सकते हैं, लेकिन इसके बजाय rs उपयोग करें। दूसरे शब्दों में, फ़ंक्शन f को परिणामों की सूची में लागू किया जाता है, जो स्वयं उत्पन्न करता है!

 fs :: [[a] -> a] fs = [...] rs :: [a] rs = [ f rs | f <- fs ] 

बेशक, यह सब अत्यधिक आलस्य पर निर्भर करता है, जबकि rs की गणना स्वयं के संदर्भ में की जाती है। आप fs की अपनी परिभाषा नहीं होने के लिए दोनों कार्यों को जोड़ सकते हैं, और वे बस rs एक पैरामीटर होंगे:

 rs fs = [ f (rs fs) | f <- fs ] 

यदि आप बारीकी से देखते हैं, तो सूचियाँ rs = loeb

इस प्रकार, loeb फ़ंक्शन फ़ंक्शन की एक सूची लेता है, और उत्पन्न होने वाले परिणामों की एक सूची की गणना करता है और उत्पन्न सूची में खुद को लागू करता है। क्या यह अजीब है? चेक? क्या यह पाला हुआ है? मैंने शर्त लगाई नहीं!

loeb

एक उदाहरण जो आपको यह समझने में मदद करेगा कि इस फ़ंक्शन के साथ कैसे काम करें:

 fs = [ const 1 , succ . (!! 0) , succ . (!! 1) , succ . (!! 2) ] 

यहाँ const a _ = a दो चर का एक फ़ंक्शन है जो हमेशा पहले का मान लौटाता है, succ x = inc संख्याओं के लिए succ x = inc वृद्धि है (अधिक सटीक रूप से, यह किसी भी गणना किए गए मानों के लिए वेतन वृद्धि का सामान्यीकरण है), (!!) सूची से n तत्व प्राप्त करने का एक फ़ंक्शन है। , (.) - 2 कार्यों की कार्यात्मक संरचना, पहले दाएं फ़ंक्शन को लागू करती है, फिर बाएं, हमारे मामले में, पहले सूची से आइटम को खींचती है, फिर वेतन वृद्धि।

यहां हमने पिछले परिणामों के संदर्भ में तत्वों की एक सूची का वर्णन किया है। const 1 हमारे पास पहला तत्व है, और यह हमेशा 1 वापस आएगा, उसके बाद हम दूसरे तत्व का मूल्य प्राप्त कर सकते हैं - succ . (!! 0) succ . (!! 0) , और आगे श्रृंखला के साथ - तीसरा, चौथा और पांचवां।

 > loeb fs [1,2,3,4] 

दिलचस्प बात यह है कि आदेश को बाएं से दाएं होना जरूरी नहीं है। आदेश उलटा हो सकता है, मुख्य बात परिपत्र पुनरावृत्ति को प्राप्त नहीं करना है (इस मामले में, फ़ंक्शन गणना समाप्त करने में सक्षम नहीं होगा)।

 fs = [ succ . (!! 1) , succ . (!! 3) , succ . (!! 0) , const 1 ] > loeb fs [3,2,4,1] 

सच एक स्प्रेडशीट की तरह लग रहा है? सेल में एक मान ज्ञात है, और बाकी किसी तरह एक दूसरे पर निर्भर हैं। जब गणना समाप्त होती है, तो प्रत्येक सेल का एक विशिष्ट मूल्य होता है। यह एक निश्चित बिंदु कॉम्बिनेटर के सामान्यीकरण जैसा दिखता है।

स्प्रेडशीट्स!

उपरोक्त उदाहरण एक आयामी तालिका के समान है। लेकिन आप अन्य फंक्शंस ले सकते हैं जो उदाहरण के लिए वास्तविकता, सरणियों के करीब हैं!

 import Data.Array import Data.List import Control.Monad import Text.Printf loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x --   e = val 0 --     val = const -- ,   (10 %)    vat ix = (* 0.1) . (! ix) --    sum' ixs = \arr -> foldl' (\acc ix -> acc + arr ! ix) 0 ixs spreadsheet = listArray ((0,0), (4,4)) -- Prices | VAT | Effective prices + total [ val 1, vat (0,0), sum' [(0,i) | i <- [0..1]], e, e , val 3, vat (1,0), sum' [(1,i) | i <- [0..1]], e, e , val 5, vat (2,0), sum' [(2,i) | i <- [0..1]], e, e , val 2, vat (3,0), sum' [(3,i) | i <- [0..1]], e, e , e, e, sum' [(i,2) | i <- [0..3]], e, e ] printArr :: Array (Int, Int) Double -> IO () printArr arr = forM_ [0..4] $ \i -> do forM_ [0..4] $ \j -> printf "%4.1f " (arr ! (i,j)) printf "\n" main = printArr $ loeb spreadsheet 

चलो इसे चलाते हैं!
उत्पादन में हम प्राप्त:

  1.0 0.1 1.1 0.0 0.0 3.0 0.3 3.3 0.0 0.0 5.0 0.5 5.5 0.0 0.0 2.0 0.2 2.2 0.0 0.0 0.0 0.0 12.1 0.0 0.0 

जहां पहले घुटने में हमारे मूल्य हैं ( val का उपयोग करके), दूसरे कॉलम में हमारे पास बाईं ओर जो कुछ भी है, उसका टैक्स है, तीसरे कॉलम में प्रभावी मूल्य है, और नीचे सभी प्रभावी कीमतों की कुल राशि है। अब आप देख सकते हैं, ऑर्डर कर सकते हैं और सब कुछ खरीद सकते हैं! जादू! :-)

moeb फ़ंक्शन

moeb loeb फ़ंक्शन की परिभाषा के साथ एक गेम का परिणाम है: क्या होगा अगर हम fmap को अनदेखा करना चाहते हैं। शुरुआत के लिए, यह फ़ंक्शन के हस्ताक्षर को केवल पागल बना देगा!

 -- [m]oeb = multi-loeb :-) moeb :: (((a -> b) -> b) -> c -> a) -> c -> a moeb fx = go where go = f ($ go) x 

और नए शब्दों में, आप loeb को फिर से परिभाषित कर सकते हैं, यह सिर्फ moeb का एक विशेष मामला moeb :

 loeb = moeb fmap 

और moeb फ़ंक्शन के पैरामीटर के लिए अन्य कार्यों का क्या उपयोग किया जा सकता है, ताकि इसका उपयोग किया जा सके?
उदाहरण के लिए, यदि हमारे पास कोई फ़ंक्शन है

 id :: a -> a id x = x 

तब:

 moeb id x = id ($ moeb id x) x = ($ moeb id x) x = x (moeb id x) --    ,   fix -- fix f = f (fix f) fix = moeb id 

जैसा कि आप देख सकते हैं, moeb fix फ़ंक्शन का एक सामान्यीकरण है।

ऐसे अन्य कार्य हैं जिनका उपयोग moeb मापदंडों के रूप में किया जा सकता है, जैसे कि traverse और foldMap , लेकिन मैं अभी भी नहीं जानता कि इसके लिए क्या उपयोगी है।