पार्सर (हास्केल)

Question

के लिए बेहतर आवेदक उदाहरण मैं Brent Yorgey Haskell course के माध्यम से काम कर रहा हूं, और मुझे आवेदक के लिए एक अच्छा उदाहरण परिभाषित करने में समस्या हो रही है।

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) } 

समारोह एक स्ट्रिंग लेता है, इनपुट की एक निश्चित राशि को पार्स करता है, और एक हो सकता है कि टपल जहां पहले मूल्य पार्सर के प्रकार है देता है, और बाकी अन-पार्स शेष है: एक पार्सर इस प्रकार परिभाषित किया गया है स्ट्रिंग का

posInt :: Parser Integer 
posInt = Parser f 
    where 
    f xs 
     | null ns = Nothing 
     | otherwise = Just (read ns, rest) 
     where (ns, rest) = span isDigit xs 

काम पार्सर के लिए एक अनुप्रयोगी उदाहरण बनाने के लिए है: उदाहरण के लिए, इस धनात्मक पूर्णांक के लिए एक पार्सर है। हम एक functor उदाहरण (जो अपेक्षाकृत सीधी-सपाट है, मुझे लगता है) के साथ शुरू:

first :: (a -> b) -> (a,c) -> (b,c) 
first f (a, c) = (f a, c) 

instance Functor Parser where 
    fmap f p = Parser f' 
    where f' s = fmap (first f) $ (runParser p) s 

और फिर मैं अनुप्रयोगी साथ मेरे हाथ की कोशिश की:

collapse (Just (Just a)) = Just a 
collapse _ = Nothing 

extract (Just a, Just b) = Just (a,b) 
extract _ = Nothing 

appliedFunc :: Parser (a->b) -> Parser a -> String -> Maybe (b, String) 
appliedFunc p1 p2 str = extract (f <*> fmap fst result2, fmap snd result2) 
    where result1 = (runParser p1) str 
     f   = fmap fst result1 
     result2 = collapse $ fmap (runParser p2) $ fmap snd result1 

instance Applicative Parser where 
    pure a = Parser (\s -> Just (a, s)) 
    p1 <*> p2 = Parser (appliedFunc p1 p2) 

... छी। तो मेरा सवाल यह है कि, मैं अपना आवेदक उदाहरण क्लीनर कैसे पढ़ सकता हूं और पढ़ने में मुश्किल हो सकता हूं? मुझे लगता है कि इस सवाल के लिए एक आसान जवाब है, लेकिन मैं अभी तक अपने सिर को चारों ओर लपेटने में सक्षम नहीं हूं।

Answer 1

मुझे लगता है कि आपको अभी तक Monad एस नहीं मिला है। जिस तरह से आप collapse और fmap का उपयोग कर रहे हैं, मुझे इंगित करता है कि आप इस समस्या को हल करने के लिए Monad एस को अनिवार्य रूप से पुनर्निर्मित कर रहे हैं, और विशेष रूप से Monad Maybe उदाहरण। वास्तव में आपके collapse इस मोनड के लिए join जैसा ही है। और वास्तव में उस का उपयोग इस समस्या को हल करने के लिए एक बहुत ही शानदार तरीका है, लेकिन शायद इस बिंदु पर कुछ हद तक "धोखाधड़ी" है। निम्नलिखित सबसे अच्छा आकार आपके कार्यों का उपयोग करते समय मैं में मिल सकता है है:

appliedFunc p1 p2 str = collapse $ fmap step1 (runParser p1 str) 
    where 
    step1 (f, str2) = collapse $ fmap step2 (runParser p2 str2) 
     where 
     step2 (x, str3) = Just (f x, str3) 

एक बार जब आप करने के लिए मिलता Monad रों उचित, आप और भी अधिक संक्षिप्त (>>=) ऑपरेटर और/या do अंकन के साथ इस पुनर्लेखन के लिए सक्षम होना चाहिए ।

एक और विकल्प जो लगभग सरल है, लेकिन मोनैड को पुनर्निर्मित करने की आवश्यकता नहीं है, Maybe एस के स्पष्ट पैटर्न मिलान का उपयोग करना है। फिर आप कुछ प्राप्त कर सकते हैं:

appliedFunc p1 p2 str = case runParser p1 str of 
    Nothing  -> Nothing 
    Just (f, str2) -> case runParser p2 str2 of 
     Nothing  -> Nothing 
     Just (x, str3) -> Just (f x, str3) 

Answer 2

यह शायद आप क्या चाहते हैं नहीं है, लेकिन मैं गुजर इस लागू करने के लिए एक बहुत संक्षिप्त तरीका है कि वहाँ में उल्लेखित करना चाहते थे:

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 

import Control.Applicative 
import Control.Monad.Trans.State 

newtype Parser a = Parser { unParser :: StateT String Maybe a } 
    deriving (Functor, Applicative, Monad, Alternative) 

runParser :: Parser a -> String -> Maybe (a, String) 
runParser = runStateT . unParser 

parser :: (String -> Maybe (a, String)) -> Parser a 
parser = Parser . StateT 

कारण यह काम करता है कि हुड के नीचे StateT के रूप में लागू किया जाता है :

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) } 

यदि आप sString के विशेषज्ञ और Maybe को m विशेषज्ञ, आपको मिलता है:

StateT String Maybe a ~ String -> Maybe (a, String) 

... जो आपके प्रकार के समान है।

instance Monad Maybe 

instance Alternative Maybe 

:

StateT आप के लिए स्वचालित रूप से प्रदान की निम्नलिखित उदाहरण हैं:

instance Monad m => Functor  (StateT s m) 
instance Monad m => Applicative (StateT s m) 
instance Monad m => Monad  (StateT s m) 

instance Alternative m => Alternative (StateT s m) 

... और हम Maybe करने के लिए उन मामलों में m विशेषज्ञ क्योंकि Maybe दोनों Alternative और Monad लागू करता है सकते हैं। .. तो इसका मतलब है कि StateT s Maybe स्वचालित रूप से Functor, Applicative है, हमारे भाग पर कोई अतिरिक्त काम किए बिना Monad और Alternative।

चाल का अंतिम भाग GeneralizedNewtypeDeriving है, जो हमें एक नए प्रकार के आवरण के माध्यम से टाइप क्लास उदाहरण उठाने देता है। चूंकि हमारे अंतर्निहित StateT प्रकार एक Functor, Applicative, Monad, और Alternative हम स्वत: अपने newtype के माध्यम से सभी चार प्रकार वर्ग उदाहरणों को जोड़कर उठा सकते है:

... deriving (Functor, Applicative, Monad, Alternative) 

... और संकलक उन्हें हमारे newtype के लिए reimplement होगा , सभी नए प्रकार के लपेटने और हमारे लिए खोलने की देखभाल कर रहे हैं।

तो अगर आप यह पता लगाने के लिए अपने पार्सर के लिए Applicative लागू करने के लिए कैसे करना चाहते हैं, तो आप अध्ययन करने के लिए कैसे ApplicativeStateT के लिए लागू किया जाता है और फिर कैसे अपने पार्सर प्रकार के लिए इसे लागू करने से निकालना चाहते हो सकता है।