मैं आपका ध्यान जस्टिन ले के एक अद्भुत ताज़ा लेख के अनुवाद पर लाता हूँ। कोड में अपने ब्लॉग में, यह लेखक व्यावहारिक समस्याओं के लिए सुंदर और सुरुचिपूर्ण कार्यात्मक समाधानों के गणितीय सार के बारे में आसान भाषा में बात करता है। यह आलेख विस्तार से उदाहरण देता है कि गणितीय संरचना को कैसे स्थानांतरित किया जाए जो विषय क्षेत्र में डेटा प्रोग्राम प्रकारों की एक प्रणाली के रूप में तुरंत तैयार हो, जैसा कि गेराल्ड और सस्मान ने "स्वचालित रूप से" लिखा था, एक काम करने वाले समाधान का नेतृत्व करता है।

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

आज हम मुक्त बीजीय संरचनाओं का उपयोग करके आवेदक नियमित अभिव्यक्ति और पार्सर ( रेगेक्स-एपेरेटिव लाइब्रेरी की भावना में) को लागू करते हैं! हास्केल में मुफ्त संरचनाएं मेरे पसंदीदा उपकरणों में से एक हैं और मैंने पहले मुक्त समूहों , मुफ्त मठों के विषय में भिन्नताएं और मोनोइड्स पर "मुक्त" आवेदनकर्ता फ़नकार के बारे में लिखा था।

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

लेख का सभी कोड "स्टैक एक्जीक्यूटेबल" के रूप में ऑनलाइन उपलब्ध है । यदि आप इसे ( ./regexp.hs ) चलाते हैं, तो GHCi सत्र सभी परिभाषाओं के साथ शुरू होगा, इसलिए आपके पास फ़ंक्शन और उनके प्रकारों के साथ खेलने का अवसर होगा।

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

नियमित भाषा

एक नियमित अभिव्यक्ति कुछ नियमित भाषा को परिभाषित करने का एक तरीका है। औपचारिक रूप से, ऐसी अभिव्यक्ति तीन मूल तत्वों से निर्मित होती है:

1. एक खाली सेट एक ऐसा तत्व है जो किसी भी चीज़ के लिए मैप नहीं करता है।
2. एक खाली स्ट्रिंग एक तटस्थ तत्व है जो तुच्छ रूप से एक रिक्त स्ट्रिंग से मेल खाता है।
3. एक शाब्दिक एक प्रतीक है जो स्वयं से मेल खाता है। बहुत से एक तत्व।

और तीन ऑपरेशनों से भी:

1. समास: RS , अभिव्यक्ति का क्रम। सेट (कार्टेशियन) का उत्पाद।
2. वैकल्पिक: R|S , अभिव्यक्ति के बीच विकल्प। सेट का संघ।
3. वेज स्टार: R* , एक अभिव्यक्ति की पुनरावृत्ति एक मनमाना संख्या (शून्य सहित)।

और वह सब जो नियमित अभिव्यक्ति करता है, कोई और अधिक, कोई कम नहीं। इन बुनियादी घटकों से, आप नियमित अभिव्यक्तियों पर अन्य सभी ज्ञात कार्यों का निर्माण कर सकते हैं - उदाहरण के लिए, a+ को aa* रूप में व्यक्त किया जा सकता है, और उपयुक्त वर्णों के विकल्प के रूप में \w जैसी श्रेणियों का प्रतिनिधित्व किया जा सकता है।

वैकल्पिक फ़नकार

जब आप नियमित अभिव्यक्तियों की संरचना को देखते हैं, तो क्या यह परिचित नहीं लगता है? यह मुझे कई प्रकार के Alternative वर्ग की याद दिलाता है। यदि कोई फ़नकार इस वर्ग का है, तो इसका मतलब है कि इसके लिए निम्नलिखित परिभाषित हैं:

1. विफलता या गणना त्रुटि के अनुरूप एक खाली तत्व।
2. pure x - एक एकल तत्व (लागू वर्ग से)।
3. ऑपरेशन <*> , अनुक्रमिक गणना का आयोजन।
4. ऑपरेशन <|> , वैकल्पिक गणनाओं का आयोजन।
5. many फ़ंक्शन शून्य या अधिक बार गणना दोहराए जाने का संचालन है।

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

Alternative वर्ग में कोई भी नया व्यक्ति Typeclassopedia का एक अच्छा परिचय पा सकता है। लेकिन हमारे लेख के ढांचे में, यह वर्ग केवल एक "दोहरे मोनॉइड" का प्रतिनिधित्व करता है, जिसमें संयोजन के दो तरीकों के साथ <*> और <|> , जो एक अर्थ में, संख्याओं के लिए संचालन * और + साथ तुलना की जा सकती है। सामान्य तौर पर, एक वैकल्पिक फ़नकार का निर्धारण करने के लिए, उपर्युक्त पाँच बिंदु और कम्यूटिविटी और वितरण के कुछ अतिरिक्त कानून पर्याप्त हैं।

 (<*>) :: Applicative f => f (a -> b) -> fa -> fb 

 (<*) :: Applicative f => fa -> fb -> fa (*>) :: Applicative f => fa -> fb -> fb 

इस प्रकार, हम नियमित अभिव्यक्तियों को एक वैकल्पिक फ़नकार, प्लस शाब्दिक चरित्र के लिए आदिम मान सकते हैं। लेकिन, उन्हें देखने का एक और तरीका है, और यह हमें सीधे मुक्त संरचनाओं की ओर ले जाता है। "वैकल्पिक फ़ंक्टर के साथ शाब्दिक" के बजाय, हम शाब्दिक को Alternative वर्ग के उदाहरण में बदल सकते हैं।

स्वतंत्रता

इस तरह लिखें। आदिम शाब्दिक के लिए टाइप करें:

 data Prim a = Prim Char a deriving Functor 

ध्यान दें कि जब से हम फंक्शनलर्स (एप्लाएंटिव, वैकल्पिक) के साथ काम करते हैं, तब हमारे सभी नियमित अभिव्यक्तियों के साथ एक निश्चित "परिणाम" जुड़ा होगा। ऐसा इसलिए है क्योंकि Functor , Functor और Alternative कक्षाओं के लिए एक उदाहरण को परिभाषित करते समय, हमारे पास एक पैरामीटर प्रकार होना चाहिए।

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

हमारे मामले में, Prim 'a' 1 :: Prim Int एक आदिम का प्रतिनिधित्व करेगा जो कि चरित्र 'a' नक्शे करता है और तुरंत व्याख्या की जाती है, जिसके परिणामस्वरूप एक इकाई होती है।

ठीक है, अब ... आइए हम अपने आदिम को free पुस्तकालय से मुक्त वैकल्पिक फ़ाइटर का उपयोग करके वांछित गणितीय संरचना दें:

 import Control.Alternative.Free type RegExp = Alt Prim 

वह सब है! यह नियमित अभिव्यक्ति के लिए हमारा पूर्ण प्रकार है! Functor प्रकार को Functor क्लास का उदाहरण घोषित करने के बाद, हमने सभी ऑपरेशंस को Alternative और Alternative कक्षाओं से प्राप्त किया है, क्योंकि इस मामले में Applicative (Alt f) और Alternative (Alt f) उदाहरण हैं। अब हमारे पास है:

• तुच्छ खाली सेट - Alternative वर्ग से empty
• खाली स्ट्रिंग - pure क्लास से pure
• लिटरल कैरेक्टर - बेसिक Prim
• सांत्वना - <*> आवेदनकर्ता वर्ग से
• वैकल्पिक - <|> Alternative वर्ग से
• क्लेन स्टार - Alternative वर्ग से many

और यह सब हमें पूरी तरह से "मुफ्त" मिला, अर्थात "मुफ्त में"!

अनिवार्य रूप से, एक स्वतंत्र संरचना स्वचालित रूप से हमें आधार प्रकार के लिए केवल एक अमूर्तता प्रदान करती है और इससे अधिक कुछ नहीं। लेकिन नियमित रूप से, स्वयं के द्वारा भी, केवल एक संरचना का प्रतिनिधित्व करते हैं: मूल तत्व और संचालन का एक सेट, न तो अधिक और न ही कम, इसलिए मुफ्त वैकल्पिक फ़नकार हमें ठीक वही प्रदान करता है जिसकी हमें आवश्यकता है। और नहीं, लेकिन कम नहीं।

कुछ सुविधाजनक आवरण कार्यों को जोड़ने के बाद ... प्रकार पर काम पूरा हो गया है!

 -- | charAs:   ,    charAs :: Char -> a -> RegExp a charAs cx = liftAlt (Prim cx) -- liftAlt :: fa -> Alt fa   --   Prim   RegExp -- | char:         char :: Char -> RegExp Char char c = charAs cc -- | string:         string :: String -> RegExp String string = traverse char -- , ? 

उदाहरण

अच्छा, चलो कोशिश करते हैं? आइए एक मैच के सफल होने की स्थिति में, (a|b)(cd)*e , जो कि रिटर्न देते हैं, यूनिट प्रकार () :

 testRegExp_ :: RegExp () testRegExp_ = void $ (char 'a' <|> char 'b') *> many (string "cd") *> char 'e' 

फ़ंक्शन void :: Functor f => fa -> f () Data.Functor पैकेज से परिणाम को छोड़ देता है, हम इसका उपयोग करते हैं, क्योंकि हम केवल तुलना की सफलता में रुचि रखते हैं। लेकिन संचालक <|> , *> और many हमारे द्वारा ठीक उसी तरह उपयोग किए जाते हैं जैसे कि यह माना जाता है कि किसी विकल्प को चुनने या चुनने पर।

यहां एक दिलचस्प और अधिक जटिल उदाहरण है, चलो उसी नियमित अभिव्यक्ति को परिभाषित करते हैं, लेकिन अब, मिलान के परिणामस्वरूप, हम प्रतिस्थापन cd की पुनरावृत्ति की संख्या की गणना करते हैं।

 testRegExp :: RegExp Int testRegExp = (char 'a' <|> char 'b') *> (length <$> many (string "cd")) <* char 'e' 

*> और <* ऑपरेटरों के संचालन में एक सूक्ष्मता है: तीर परिणाम को इंगित करता है जिसे बचाया जाना चाहिए। और many (string "cd") :: RegExp [String] दोहराए जाने वाले तत्वों की एक सूची देता है, हम कर सकते हैं, फ़नकार के अंदर शेष, पुनरावृत्तियों की संख्या प्राप्त करके इस सूची की लंबाई की गणना करें।

इसके अलावा, GHC -XApplicativeDo संकलक -XApplicativeDo do-notation का उपयोग करके अपनी अभिव्यक्ति लिखने की अनुमति देता -XApplicativeDo , जिसे समझना आसान है:

 testRegExpDo :: RegExp Int testRegExpDo = do char 'a' <|> char 'b' cds <- many (string "cd") char 'e' pure (length cds) 

यह सब कुछ इसी तरह है कि हम एक स्ट्रिंग का परिणाम कैसे प्राप्त करते हैं, जो एक नियमित अभिव्यक्ति का उपयोग करके स्ट्रिंग को पार्स करने का परिणाम है। यहाँ एक उदाहरण है रूबी में:

 irb> /(a|b)((cd)*)e/.match("acdcdcdcde")[2] => "cdcdcdcd" 

एकमात्र अंतर यह है कि हमने पुनरावृत्ति की संख्या की गणना करने के लिए कुछ पोस्ट-प्रोसेसिंग को जोड़ा।

यहां एक और सुविधाजनक नियमित \d जो 0 से 9 तक की संख्या से मेल खाता है और एक नंबर देता है:

 digit :: RegExp Int digit = asum [ charAs (intToDigit i) i | i <- [0..9] ] 

यहां, Control.Applicative.Alternative पैकेज से asum फ़ंक्शन सूची आइटम asum [x,y,z] = x <|> y <|> z से एक चयन का प्रतिनिधित्व करता है, और intToDigit फ़ंक्शन Data.Char पैकेज में परिभाषित किया गया है। और, फिर से, हम काफी सुरुचिपूर्ण चीजें बना सकते हैं, उदाहरण के लिए, वर्ग कोष्ठक में संख्या के अनुरूप अभिव्यक्ति \[\d\] :

 bracketDigit :: RegExp Int bracketDigit = char '[' *> digit <* char ']' 

पदच्छेद

ठीक है, ठीक है, हम सब किया था वर्णन, चयन, और पुनरावृत्ति के साथ एक शाब्दिक के लिए डेटा प्रकार। बहुत बढ़िया! लेकिन क्या हमें वास्तव में एक स्ट्रिंग की नियमित अभिव्यक्ति के साथ मेल खाना चाहिए, है ना? एक मुफ्त वैकल्पिक फ़नकार कैसे हमारी मदद कर सकता है? वास्तव में, यह बहुत मदद करेगा। आइए ऐसा करने के दो तरीके देखें!

वैकल्पिक फ़नकार को उतारें

स्वतंत्रता क्या है?

एक स्वतंत्र संरचना का उपयोग करने का विहित तरीका उपयुक्त बीजगणित का उपयोग करके इसे एक ठोस संरचना में मोड़ना है। उदाहरण के लिए, foldMap ट्रांसफ़ॉर्म एक मुक्त foldMap (सूची) को Monoid वर्ग के किसी भी उदाहरण के मूल्य में बदल देता है:

 foldMap :: Monoid m => (a -> m) -> ([a] -> m) 

foldMap फ़ंक्शन रूपांतरण को a -> m foldMap a -> m के साथ रूपांतरण [a] -> m में बदल देता है [a] -> m (या, FreeMonoid a -> m )। सामान्य विचार यह है कि एक स्वतंत्र संरचना का उपयोग आपको इसके विशिष्ट उपयोग को "बाद के लिए" स्थगित करने की अनुमति देता है, जिससे रचना समय और संरचना का उपयोग करने का समय अलग हो जाता है।

उदाहरण के लिए, हम संख्याओं से मुक्त मोनॉइड का निर्माण कर सकते हैं:

 -- |  "" `Int`     `Int`,  `liftAlt`. liftFM :: Int -> [Int] liftFM x = [x] myMon :: [Int] myMon = liftFM 1 <> liftFM 2 <> liftFM 3 <> liftFM 4 

और अब हम तय कर सकते हैं कि हम ऑपरेशन की व्याख्या कैसे करना चाहते हैं <> :
शायद यह जोड़?

 ghci> foldMap Sum myMon Sum 10 -- 1 + 2 + 3 + 4 

या गुणा?

 ghci> foldMap Product myMon Product 24 -- 1 * 2 * 3 * 4 

या शायद अधिकतम संख्या की गणना?

 ghci> foldMap Max myMon Max 4 -- 1 `max` 2 `max` 3 `max` 4 

सबसे पहले संख्या 1, 2, 3, और 4 के एक नि: शुल्क संग्रह का निर्माण करके किसी विशेष मोनॉयड के चयन को स्थगित करने का विचार है। संख्याओं पर एक मुक्त मोनॉइड उनके ऊपर की संरचना को निर्धारित करता है जिसकी आपको आवश्यकता है, कोई और अधिक, कोई कम नहीं। foldMap उपयोग करने के लिए foldMap हम एक विशेष मोनॉइड के लिए <> ऑपरेटर को पास करके "आधार प्रकार को कैसे देखें" निर्दिष्ट करते हैं।

एक State फनकार में व्याख्या

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

इस फ़नकार के लिए उत्पाद <*> में राज्य परिवर्तनों के क्रम को व्यवस्थित करना शामिल है। हमारे मामले में, राज्य के तहत, हम पार्स किए गए स्ट्रिंग के शेष पर विचार करेंगे, ताकि अनुक्रमिक पार्सिंग ऑपरेशन के लिए सबसे अच्छा मैच <*> ।

और इसका योग <|> बैकट्रैकिंग की तरह काम करता है, विफलता के मामले में विकल्प की वापसी के साथ एक खोज। यह अंतिम सफल निष्पादन के बाद से राज्य को बनाए रखता है और यदि विकल्प असफल रूप से चुना जाता है तो यह वापस आ जाता है। यह बिल्कुल ऐसा व्यवहार है जो हम अभिव्यक्ति से उम्मीद करते हैं R|S

अंत में, एक मुफ्त वैकल्पिक runAlt लिए एक प्राकृतिक परिवर्तन को runAlt कहा जाता है:

 runAlt :: Alternative f => (forall b. pb -> fb) -> Alt pa -> fa 

या, RegExp टाइप करें:

 runAlt :: Alternative f => (forall b. Prim b -> fb) -> RegExp a -> fa 

यदि आप RankN प्रकार ( forall b. कंस्ट्रक्शन के साथ) से परिचित नहीं हैं, तो आप यहां एक अच्छा परिचय देख सकते हैं। यहाँ मुद्दा यह है कि आपको एक runAlt फ़ंक्शन प्रदान करना होगा जो कि किसी भी b लिए Prim b साथ काम करता है, और उदाहरण के लिए, Int और Bool जैसे किसी विशेष प्रकार का नहीं। यह है, जैसा कि foldMap साथ है foldMap हमें केवल यह निर्दिष्ट करने की आवश्यकता है कि आधार प्रकार के साथ क्या करना है। हमारे मामले में, इस प्रश्न का उत्तर दें: "टाइप Prim साथ क्या करने की आवश्यकता है?"

 processPrim :: Prim a -> StateT String Maybe a processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

यह StateT String Maybe के संदर्भ में एक कार्रवाई के रूप में Prim व्याख्या है, जहां राज्य एक StateT String Maybe स्ट्रिंग है। आपको याद दिला दूं कि Prim में मैचिंग कैरेक्टर c और इसके x के कुछ मूल्य के रूप में इसकी व्याख्या के बारे में जानकारी है। Prim प्रोसेसिंग में निम्नलिखित चरण होते हैं:

• Get का उपयोग get राज्य (स्ट्रिंग का अभी तक पार्स नहीं किया गया हिस्सा) प्राप्त करते हैं और तुरंत अपने पहले चरित्र का प्रिंट निकालते हैं और शेष रहते हैं। यदि रेखा खाली है, तो एक विकल्प वापस आ जाएगा। ( StateT शायद StateT अंदर काम करता है, और अगर यह ब्लॉक के अंदर <- ऑपरेटर के दाईं ओर पैटर्न से मेल करना असंभव है, तो गणना परिणाम के साथ समाप्त हो जाएगी, अर्थात, Nothing । लगभग। ट्रांस। )
• हम दिए गए चरित्र के साथ वर्तमान चरित्र से मेल खाने के लिए गार्ड अभिव्यक्ति का उपयोग करते हैं। विफलता के मामले में, empty लौटा दिया जाता है, और हम वैकल्पिक विकल्प के पास जाते हैं।
• हम अपनी "पूंछ" के साथ पार्स स्ट्रिंग को बदलकर राज्य बदलते हैं, क्योंकि इस क्षण तक वर्तमान चरित्र को पहले से ही सफलतापूर्वक पार किया जा सकता है।
• हम वही लौटते हैं जो कि आदिम को वापस लौटाना चाहिए।

आप इस फ़ंक्शन का उपयोग पहले से ही RegEx को स्ट्रिंग उपसर्ग में मैप करने के लिए कर सकते हैं। ऐसा करने के लिए, आपको runAlt और runStateT का उपयोग करके गणना शुरू करने की आवश्यकता है, एक तर्क के रूप में पिछले फ़ंक्शन को पार्स किए गए स्ट्रिंग को पास करना:

 matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) 

बस इतना ही! आइए देखें कि हमारा पहला समाधान कैसे काम करता है:

 ghci> matchPrefix testRegexp_ "acdcdcde" Just () ghci> matchPrefix testRegexp_ "acdcdcdx" Nothing ghci> matchPrefix testRegexp "acdcdcde" Just 3 ghci> matchPrefix testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchPrefix digit "9" Just 9 ghci> matchPrefix bracketDigit "[2]" Just 2 ghci> matchPrefix (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchPrefix (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

रुको, वह क्या था?

ऐसा लगता है कि सब कुछ आपकी अपेक्षा से थोड़ा तेज हुआ। एक मिनट पहले हमने अपना आदिम लिखा, और फिर फिर से! और वर्किंग पार्सर तैयार है। यहाँ, वास्तव में, सभी प्रमुख कोड, हास्केल में कुछ पंक्तियाँ:

 import Control.Monad.Trans.State (evalStateT, put, get) import Control.Alternative.Free (runAlt, Alt) import Control.Applicative import Control.Monad (guard) data Prim a = Prim Char a deriving Functor type RegExp = Alt Prim matchPrefix :: RegExp a -> String -> Maybe a matchPrefix re = evalStateT (runAlt processPrim re) where processPrim (Prim cx) = do d:ds <- get guard (c == d) put ds pure x 

और क्या हमारे पास पूरी तरह कार्यात्मक नियमित अभिव्यक्ति पार्सर है? क्या हुआ?

याद रखें कि अमूर्तता के उच्च स्तर पर, Alt Prim पहले से ही pure , empty , Prim , <*> , <|> और <|> और इसकी संरचना में many (इस ऑपरेटर के साथ एक अप्रिय सूक्ष्मता है, लेकिन बाद में उस पर और अधिक)। runAlt जो runAlt करता है, वह pure , empty , <*> , <|> , और many ऑपरेटरों के व्यवहार को नियंत्रित करने के लिए एक विशेष वैकल्पिक StateT String Maybe (हमारे मामले में StateT String Maybe ) के व्यवहार का उपयोग करता है। हालांकि, StateT में Prim समान एक अंतर्निहित ऑपरेटर नहीं है, और इसके लिए हमें processPrim लिखने की processPrim ।

तो, Prim प्रकार के लिए, runAlt फ़ंक्शन प्रक्रियाप्रीम का उपयोग करता है, और pure , empty , <*> , <|> , और many , Alternative वर्ग का एक उपयुक्त उदाहरण उपयोग किया जाता है। इस प्रकार, 83% काम हमारे लिए StateT द्वारा किया जाता है, और शेष 17% StateT द्वारा किया जाता है। सच में, यह कुछ हद तक निराशाजनक है। एक पूछ सकता है: Alt रैपर के साथ शुरुआत करना क्यों आवश्यक था? क्यों नहीं तुरंत परिभाषित करें RegExp = StateT String Maybe और उपयुक्त आदिम char :: Char -> StateT String Maybe Char ? यदि सब कुछ स्टेटटी फ़नकार में किया जाता है, तो Alt साथ परेशान क्यों है - एक मुफ्त वैकल्पिक फ़नकार?

StateT पर Alt मुख्य लाभ यह है कि StateT ... एक बहुत शक्तिशाली उपकरण है। लेकिन वास्तव में, वह बेतुकी बात करने के लिए शक्तिशाली है। इसका उपयोग सबसे अधिक विविध कम्प्यूटेशंस और संरचनाओं की एक बड़ी संख्या का प्रतिनिधित्व करने के लिए किया जा सकता है, और, अप्रिय रूप से, किसी ऐसी चीज़ की कल्पना करना आसान है जो एक नियमित अभिव्यक्ति नहीं है। मान लीजिए कि कुछ मूल शब्द जैसे put "hello" :: StateT String Maybe () किसी भी मान्य नियमित अभिव्यक्ति से मेल नहीं खाता है, लेकिन यह उसी प्रकार का है जैसे कि RegExp () । इस प्रकार, जबकि हम कहते हैं कि Alt Prim एक नियमित अभिव्यक्ति से मेल खाता है, और अधिक नहीं, लेकिन कम नहीं, हम StateT String Maybe साथ भी StateT String Maybe नहीं कह सकते। Alt Prim प्रकार एक नियमित अभिव्यक्ति का सही प्रतिनिधित्व है। इसकी सहायता से व्यक्त की जा सकने वाली प्रत्येक चीज़ एक नियमित अभिव्यक्ति है, लेकिन ऐसी कोई भी चीज़ जो ऐसी अभिव्यक्ति नहीं है, इसकी सहायता से व्यक्त नहीं की जा सकती है। यहाँ, हालांकि, हास्केल के आलस्य से जुड़ी कुछ अप्रिय सूक्ष्मताएँ भी हैं, इस पर बाद में और भी।

यहां हम StateT केवल एक संदर्भ के रूप में उपयोग कर सकते हैं
नियमित अभिव्यक्ति व्याख्याएं - एक पार्सर के रूप में। लेकिन आप RegExp का उपयोग करने के अन्य तरीकों की कल्पना कर सकते हैं। उदाहरण के लिए, हमें इसके StateT प्रतिनिधित्व की आवश्यकता हो सकती है, जो कि StateT अनुमति नहीं देगा।

हम यह नहीं कह सकते हैं कि StateT String Maybe एक नियमित अभिव्यक्ति है, केवल यह कि यह StateT String Maybe नियमित व्याकरण पर आधारित एक पार्सर का प्रतिनिधित्व कर सकता है। लेकिन Alt Prim बारे में Alt Prim हम यह निश्चित रूप से कह सकते हैं कि यह एक नियमित अभिव्यक्ति है ( जैसा कि गणितज्ञ कहते हैं, वे समरूपतावाद के लगभग बराबर हैं। लगभग। )

मुक्त संरचना का प्रत्यक्ष उपयोग

यह सब, ज़ाहिर है, बहुत अच्छा है, लेकिन क्या होगा अगर हम 83% काम को उस प्रकार के लिए कोड करने के लिए स्थानांतरित नहीं करना चाहते हैं जो हमारे लिए किसी व्यक्ति द्वारा लिखा गया था। क्या पार्सर लिखने के लिए सीधे मुक्त Alt संरचना का उपयोग करना संभव है? यह प्रश्न इस तरह से है: एक फ़ंक्शन को कैसे लिखना है जो केवल foldMap का उपयोग करने के बजाय निर्माण (:) और [] मिलान करके) प्रक्रियाओं को सूचीबद्ध करता है? एक विशिष्ट मोनॉइड को काम सौंपने के बजाय सीधे इस संरचना के साथ कैसे काम करें?

खुशी है कि आपने पूछा! आइए एक नज़र डालते हैं मुफ्त वैकल्पिक फ़नकार की परिभाषा पर:

 newtype Alt fa = Alt { alternatives :: [AltF fa] } data AltF fa = forall r. Ap (fr) (Alt f (r -> a)) | Pure a 

यह पारस्परिक पुनरावृत्ति के माध्यम से परिभाषित एक असामान्य प्रकार है, इसलिए यह बहुत भ्रामक लग सकता है। इसे समझने का एक तरीका यह कल्पना करना है कि Alt xs में <|> ऑपरेटर के उपयोग से बनने वाले विकल्पों की एक श्रृंखला है। AltF , f , <*> ( ).

AltF fa [fr] , r . Ap (:) , fr , Pure — [] . forall r. -XExistentialQuantification .

, Alt f , . , ( ) <*> <|> , , [a] <> .

, RegExp a -> String -> Maybe a , , . : .

, Alt . , , .

 matchAlts :: RegExp a -> String -> Maybe a matchAlts (Alt res) xs = asum [ matchChain re xs | re <- res ] 

asum :: [Maybe a] -> Maybe a , Just . ( , Maybe a Alternative — Nothing , <|> . . . )

. AltF , Ap Pure :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = _ matchChain (Pure x) cs = _ 

" ": GHC "", , , . ( Haskell "" (holes) , _ , . . . ) :

 matchChain :: AltF Prim a -> String -> Maybe a matchChain (Ap (Prim cx) next) cs = case cs of [] -> Nothing d:ds | c == d -> matchAlts (($ x) <$> next) ds | otherwise -> Nothing matchChain (Pure x) _ = Just x 

Ap ( (:) ), , - . , . Prim r , , next :: RegExp (r -> a) . , next . , "" , Nothing . , Pure x ( [] ), , , .

, , . , , " " Ap , Pure , AltF .., .

:

 ghci> matchAlts testRegexp_ "acdcdcde" Just () ghci> matchAlts testRegexp_ "acdcdcdx" Nothing ghci> matchAlts testRegexp "acdcdcde" Just 3 ghci> matchAlts testRegexp "bcdcdcdcdcdcdcde" Just 7 ghci> matchAlts digit "9" Just 9 ghci> matchAlts bracketDigit "[2]" Just 2 ghci> matchAlts (many bracketDigit) "[2][3][4][5]" Just [2,3,4,5] ghci> matchAlts (sum <$> many bracketDigit) "[2][3][4][5]" Just 14 

?

foldMap . , , foldMap, , , , ! , — , — (:) [] .

, , : , , , (:) , [] . , . , [1,2,3] <> [4] , [1] <> [2,3] <> [4] . , , .

. , :

 data RegExp a = Empty | Pure a | Prim Char a | forall r. Seq (RegExp r) (RegExp (r -> a)) | Union (RegExp a) (RegExp a) | Many (RegExp a) 

RegExp , . . , RegExp :

 -- | a|(b|c) abc1 :: RegExp Int abc1 = Prim 'a' 1 `Union` (Prim 'b' 2 `Union` Prim 'c' 3) -- | (a|b)|c abc2 :: RegExp Int abc2 = (Prim 'a' 1 `Union` Prim 'b' 2) `Union` Prim 'c' 3 

, .

Alt Prim , , , . , matchAlts , . (a|b)|c a|(b|c) . Alt . , , .

, , (a|b)|c , (a|b)|c , , , RegExp . Alt , .

, , Alt , Alt Prim . , Alt Prim a|a a . , Alt f f . , : . , , , .

, . , , . RegExp , , — .

, Haskell. , - [a] . ( , - , "" $$$\bot$, - "" . . . )

: a|aa|aaa|aaaa|aaaaa|aaaaaa|... , ( , , , . . . ). , Haskell . , Alt many . , a* a|aa|aaa|aaaa|aaaaa|aaaaaa|... , . - many (char 'a') , . Haskell Alt , .

, , , , (), . , many .

, ! "" Alt , Control.Alternative.Free.Final , many (, , ).

, , runAlt . , Alternative , many ( RE regex-applicative ) . , Haskell , , , many .

, . ( ), ( , , . . ). matchPrefix , , , . , , , , . , GHC .

, , tails ( ) mapMaybe ( ). , , listToMaybe .

 matches :: RegExp a -> String -> [a] matches re = mapMaybe (matchPrefix re) . tails firstMatch :: RegExp a -> String -> Maybe a firstMatch re = listToMaybe . matches re 

, , matchPrefix Nothing , listToMaybe , Nothing ( , . . . ).

, . , , — , . , . , , , .

Alt Prim , : , , , .

? . :

 data Prim a = Only Char a --    | Letter a --     | Digit (Int -> a) --    , | Wildcard (Char -> a) --    , | Satisfy (Char -> Maybe a) --    , --   

, . .

, , . runAlt Alt .

(). , , , , . | . ( , . . . ). , - . , MonadPlus - , , . , .

, , . , !