इस पाइथन को हास्केल में कैसे अनुवाद करें?

Question

मैं हास्केल सीख रहा हूं और एक अभ्यास के रूप में मैं कोड के बाद हैस्केल को पढ़ने के बाद read_from फ़ंक्शन लिखने की कोशिश कर रहा हूं। पीटर Norvig की योजना दुभाषिया से लिया गया। क्या ऐसा कोई आसान तरीका है?

def read(s): 
    "Read a Scheme expression from a string." 
    return read_from(tokenize(s)) 

parse = read 

def tokenize(s): 
    "Convert a string into a list of tokens." 
    return s.replace('(',' (').replace(')',') ').split() 

def read_from(tokens): 
    "Read an expression from a sequence of tokens." 
    if len(tokens) == 0: 
     raise SyntaxError('unexpected EOF while reading') 
    token = tokens.pop(0) 
    if '(' == token: 
     L = [] 
     while tokens[0] != ')': 
      L.append(read_from(tokens)) 
     tokens.pop(0) # pop off ')' 
     return L 
    elif ')' == token: 
     raise SyntaxError('unexpected)') 
    else: 
     return atom(token) 

def atom(token): 
    "Numbers become numbers; every other token is a symbol." 
    try: return int(token) 
    except ValueError: 
     try: return float(token) 
     except ValueError: 
      return Symbol(token) 

Answer 1

हास्केल में, आप एक एल्गोरिदम का उपयोग नहीं करेंगे जो उस डेटा को म्यूट करता है जो इसे संचालित करता है। तो नहीं, ऐसा करने का कोई सीधा तरीका नहीं है। हालांकि, चर को अद्यतन करने से बचने के लिए कोड को रिकर्सन का उपयोग करके फिर से लिखा जा सकता है। नीचे दिए गए समाधान MissingH पैकेज का उपयोग करता है क्योंकि Haskell परेशानियों में replace फ़ंक्शन नहीं है जो स्ट्रिंग पर काम करता है।

import Data.String.Utils (replace) 
import Data.Tree 
import System.Environment (getArgs) 

data Atom = Sym String | NInt Int | NDouble Double | Para deriving (Eq, Show) 

type ParserStack = (Tree Atom, Tree Atom) 

tokenize = words . replace "(" " (" . replace ")" ") " 

atom :: String -> Atom 
atom tok = 
    case reads tok :: [(Int, String)] of 
    [(int, _)] -> NInt int 
    _ -> case reads tok :: [(Double, String)] of 
     [(dbl, _)] -> NDouble dbl 
     _ -> Sym tok 

empty = Node $ Sym "dummy" 
para = Node Para 

parseToken (Node _ stack, Node _ out) "(" = 
    (empty $ stack ++ [empty out], empty []) 
parseToken (Node _ stack, Node _ out) ")" = 
    (empty $ init stack, empty $ (subForest (last stack)) ++ [para out]) 
parseToken (stack, Node _ out) tok = 
    (stack, empty $ out ++ [Node (atom tok) []]) 

main = do 
    (file:_) <- getArgs 
    contents <- readFile file 
    let tokens = tokenize contents 
     parseStack = foldl parseToken (empty [], empty []) tokens 
     schemeTree = head $ subForest $ snd parseStack 
    putStrLn $ drawTree $ fmap show schemeTree 

foldl haskeller की बुनियादी संरचित प्रत्यावर्तन उपकरण है और यह आपके जबकि पाश और read_from को पुनरावर्ती कॉल के रूप में एक ही उद्देश्य में कार्य करता है। मुझे लगता है कि कोड को बहुत सुधार किया जा सकता है, लेकिन मुझे हास्केल में इतना उपयोग नहीं किया जाता है।नीचे अजगर को ऊपर की एक लगभग सीधे लिप्यंतरण है:

from pprint import pprint 
from sys import argv 

def atom(tok): 
    try: 
     return 'int', int(tok) 
    except ValueError: 
     try: 
      return 'float', float(tok) 
     except ValueError: 
      return 'sym', tok 

def tokenize(s): 
    return s.replace('(',' (').replace(')',') ').split() 

def handle_tok((stack, out), tok): 
    if tok == '(': 
     return stack + [out], [] 
    if tok == ')': 
     return stack[:-1], stack[-1] + [out] 
    return stack, out + [atom(tok)] 

if __name__ == '__main__': 
    tokens = tokenize(open(argv[1]).read()) 
    tree = reduce(handle_tok, tokens, ([], []))[1][0] 
    pprint(tree) 

Answer 2

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

parse :: String -> SchemeExpr 
parse s = readFrom (tokenize s) 

अजगर docstring ने कहा, "एक स्ट्रिंग से एक योजना अभिव्यक्ति पढ़ने के लिए", तो मैं बस प्रकार हस्ताक्षर() के रूप में इस एन्कोडिंग की स्वतंत्रता ले लिया। वह डॉकस्ट्रिंग अप्रचलित हो जाता है क्योंकि प्रकार एक ही जानकारी को व्यक्त करता है। अब ... SchemeExpr है? आपके कोड के अनुसार, एक योजना अभिव्यक्ति एक int, float, प्रतीक, या योजना अभिव्यक्तियों की सूची हो सकती है। चलिए एक डेटा प्रकार बनाते हैं जो इन विकल्पों का प्रतिनिधित्व करता है।

data SchemeExpr 
    = SInt Int 
    | SFloat Float 
    | SSymbol String 
    | SList [SchemeExpr] 
    deriving (Eq, Show) 

आदेश हास्केल बताने के लिए कि Int हम साथ एक SchemeExpr के रूप में व्यवहार किया जाना चाहिए काम कर रहे हैं, हम SInt के साथ टैग की जरूरत है। इसी तरह अन्य संभावनाओं के साथ। आइए tokenize पर जाएं।

tokenize :: String -> [Token] 

फिर, docstring एक प्रकार हस्ताक्षर में बदल जाता है: Token रों की एक सूची में एक String बदल जाते हैं। खैर, टोकन क्या है? यदि आप कोड को देखते हैं, तो आप देखेंगे कि बाएं और दाएं पैर के पात्र स्पष्ट रूप से विशेष टोकन हैं, जो विशेष व्यवहार को संकेत देते हैं। और कुछ भी है ... अनन्य। जबकि हम अन्य टोकन से माता-पिता को अधिक स्पष्ट रूप से अलग करने के लिए डेटा प्रकार बना सकते हैं, चलिए मूल पायथन कोड के करीब थोड़ा चिपकने के लिए स्ट्रिंग का उपयोग करें।

type Token = String 

अब tokenize लिखने का प्रयास करें। सबसे पहले, चलिए चेनिंग चेनिंग को पाइथन की तरह थोड़ा और देखने के लिए एक त्वरित छोटा ऑपरेटर लिखते हैं। हास्केल में, आप अपने स्वयं के ऑपरेटरों को परिभाषित कर सकते हैं।

(|>) :: a -> (a -> b) -> b 
x |> f = f x 

tokenize s = s |> replace "(" " (" 
       |> replace ")" ") " 
       |> words 

wordssplit की हास्केल का संस्करण है। हालांकि, हास्केल में replace का कोई पूर्व-पका हुआ संस्करण नहीं है जिसे मैं जानता हूं। आप splitOn और intercalate के लिये दस्तावेज पढ़ें

-- add imports to top of file 
import Data.List.Split (splitOn) 
import Data.List (intercalate) 

replace :: String -> String -> String -> String 
replace old new s = s |> splitOn old 
         |> intercalate new 

, इस सरल एल्गोरिदम सही समझ बनाने चाहिए: यहाँ एक है कि चाल करना चाहिए। हास्केलर्स आमतौर पर इसे replace old new = intercalate new . splitOn old के रूप में लिखेंगे, लेकिन मैंने आसानी से पाइथन दर्शकों की समझ के लिए |> का उपयोग किया था।

ध्यान दें कि replace तीन तर्क लेता है, लेकिन ऊपर मैंने केवल दो के साथ इसका आह्वान किया है। हास्केल में आप आंशिक रूप से किसी भी फ़ंक्शन को लागू कर सकते हैं, जो कि बहुत साफ है। |> यूनिक्स पाइप की तरह काम करता है, अगर आप अधिक प्रकार की सुरक्षा को छोड़कर नहीं बता सकते हैं।

---

अभी भी मेरे साथ? आइए atom पर जाएं। वह घोंसला तर्क थोड़ा बदसूरत है, इसलिए चलो इसे साफ करने के लिए थोड़ा अलग दृष्टिकोण आज़माएं। हम Either प्रकार का उपयोग बहुत अच्छी प्रस्तुति के लिए करेंगे।

atom :: Token -> SchemeExpr 
atom s = Left s |> tryReadInto SInt 
       |> tryReadInto SFloat 
       |> orElse (SSymbol s) 

हास्केल automagical coersion कार्यों int और float नहीं है, तो बजाय हम tryReadInto का निर्माण करेगा। यहां बताया गया है कि यह कैसे काम करता है: हम Either मूल्यों के आसपास धागे पर जा रहे हैं। एक Either मान या तो Left या Right है। परंपरागत रूप से, Left त्रुटि या विफलता को सिग्नल करने के लिए प्रयोग किया जाता है, जबकि Right सफलता या समापन संकेत करता है। हास्केल में, पायथन-एस्क्यू फ़ंक्शन कॉल चेनिंग अनुकरण करने के लिए, आप केवल "स्वयं" तर्क को अंतिम के रूप में रखते हैं।

tryReadInto :: Read a => (a -> b) -> Either String b -> Either String b 
tryReadInto f (Right x) = Right x 
tryReadInto f (Left s) = case readMay s of 
    Just x -> Right (f x) 
    Nothing -> Left s 

orElse :: a -> Either err a -> a 
orElse a (Left _) = a 
orElse _ (Right a) = a 

tryReadInto निर्धारित करने के लिए जो टाइप इसे में स्ट्रिंग पार्स करने का प्रयास कर रहा है में प्रकार निष्कर्ष पर निर्भर करता है। यदि पार्स विफल रहता है, तो यह Left स्थिति में समान स्ट्रिंग को पुन: उत्पन्न करता है। यदि यह सफल होता है, तो यह वही कार्य करता है जो कार्य करता है और परिणाम Right स्थिति में रखता है। orElse हमें पूर्व गणना विफल होने के मामले में मूल्य प्रदान करके Either को समाप्त करने की अनुमति देता है। क्या आप देख सकते हैं कि Either यहां अपवादों के प्रतिस्थापन के रूप में कार्य करता है? चूंकि पाइथन कोड में ValueException एस हमेशा कार्य के अंदर पकड़े गए हैं, हम जानते हैं कि atom कभी भी को अपवाद नहीं उठाएगा। इसी प्रकार, हास्केल कोड में, भले ही हमने फ़ंक्शन के अंदर Either का उपयोग किया, फिर भी इंटरफ़ेस जिसे हम बेनकाब करते हैं वह शुद्ध है: Token -> SchemeExpr, कोई बाहरी रूप से दिखाई देने वाले दुष्प्रभाव नहीं।

---

ठीक है, चलो read_from पर जाएं। सबसे पहले, खुद से सवाल पूछें: इस समारोह के किन दुष्प्रभाव हैं? यह tokenspop के माध्यम से अपने तर्क को बदलता है, और इसमें L नाम की सूची में आंतरिक उत्परिवर्तन है। यह SyntaxError अपवाद भी उठाता है। इस बिंदु पर, अधिकांश हास्केलर्स अपने हाथों को फेंक देंगे "ओह नोस! साइड इफेक्ट्स! सकल!" लेकिन सच्चाई यह है कि हास्केलर हर समय साइड इफेक्ट्स का भी उपयोग करते हैं। हम लोगों को डराने और हर कीमत पर सफलता से बचने के लिए बस उन्हें "मोनैड" कहते हैं। उत्परिवर्तन State मोनैड के साथ पूरा किया जा सकता है, और Either मोनड (आश्चर्य!) के साथ अपवाद। हम दोनों एक ही समय में उपयोग करना चाहते हैं, इसलिए हम वास्तव में "मोनैड ट्रांसफार्मर" का उपयोग करेंगे, जिसे मैं थोड़ा सा समझाऊंगा। यह नहीं है कि डरावना है, एक बार जब आप क्रुफ्ट को देखना सीखते हैं।

सबसे पहले, कुछ उपयोगिताओं। ये कुछ साधारण नलसाजी संचालन हैं। raise हमें पायथन में "अपवाद उठाने" देगा, और whileM हमें पायथन में थोड़ी देर के लूप लिखने देगा। उत्तरार्द्ध के लिए, हमें बस यह स्पष्ट करना होगा कि प्रभावों के किस क्रम में होना चाहिए: पहले स्थिति की गणना करने के लिए प्रभाव का प्रदर्शन करें, फिर यदि यह True है, तो शरीर और लूप के प्रभावों को फिर से करें।

import Control.Monad.Trans.State 
import Control.Monad.Trans.Class (lift) 

raise = lift . Left 

whileM :: Monad m => m Bool -> m() -> m() 
whileM mb m = do 
    b <- mb 
    if b 
    then m >> whileM mb m 
    else return() 

हम फिर से एक शुद्ध इंटरफ़ेस का पर्दाफाश करना चाहते हैं।हालांकि, एक मौका है कि SyntaxError होगा, इसलिए हम प्रकार हस्ताक्षर में इंगित करेंगे कि परिणाम या तोSchemeExpr या SyntaxError होगा। यह याद दिलाता है कि जावा में कैसे आप एनोटेट कर सकते हैं कि एक विधि कौन सा अपवाद उठाएगी। ध्यान दें कि parse के प्रकार हस्ताक्षर को भी बदलना है, क्योंकि यह SyntaxError को बढ़ा सकता है।

data SyntaxError = SyntaxError String 
       deriving (Show) 

parse :: String -> Either SyntaxError SchemeExpr 

readFrom :: [Token] -> Either SyntaxError SchemeExpr 
readFrom = evalStateT readFrom' 

हम इस टोकन सूची है कि में पारित हो जाता है पर एक स्टेटफुल गणना प्रदर्शन करने के लिए जा रहे हैं। अजगर के विपरीत, तथापि, हम नहीं फोन करने वाले के लिए कठोर हो सकता है और बहुत सूची हमें पारित कर दिया उत्परिवर्तित जा रहे हैं। इसके बजाए, हम अपनी खुद की राज्य की जगह स्थापित करेंगे और इसे टोकन सूची में शुरू करेंगे। हम do नोटेशन का उपयोग करेंगे, जो यह दिखने के लिए सिंटैक्टिक चीनी प्रदान करता है जैसे हम प्रोग्रामिंग अनिवार्य रूप से कर रहे हैं। StateT मोनैड ट्रांसफार्मर हमें get, put, और modify राज्य संचालन देता है।

readFrom' :: StateT [Token] (Either SyntaxError) SchemeExpr 
readFrom' = do 
    tokens <- get 
    case tokens of 
    [] -> raise (SyntaxError "unexpected EOF while reading") 
    (token:tokens') -> do 
     put tokens' -- here we overwrite the state with the "rest" of the tokens 
     case token of 
     "(" -> (SList . reverse) `fmap` execStateT readWithList [] 
     ")" -> raise (SyntaxError "unexpected close paren") 
     _ -> return (atom token) 

मैं बाहर विभाजित कर दिया है कोड, का एक अलग हिस्सा में readWithList भाग क्योंकि मैं तुम्हें प्रकार हस्ताक्षर देखना चाहते हैं। कोड का यह भाग नया स्कोप प्रस्तुत करता है, इसलिए हम मोनैड स्टैक के शीर्ष पर बस StateT लेयर करते हैं जो हमारे पास पहले था। अब, get, put, और modify संचालन पाइथन कोड में L नामक चीज़ पर देखें। यदि हम tokens पर इन परिचालनों को निष्पादित करना चाहते हैं, तो हम मोनैड स्टैक की एक परत को दूर करने के लिए क्रम में lift के साथ ऑपरेशन को आसानी से पेश कर सकते हैं।

readWithList :: StateT [SchemeExpr] (StateT [Token] (Either SyntaxError))() 
readWithList = do 
    whileM ((\toks -> toks !! 0 /= ")") `fmap` lift get) $ do 
    innerExpr <- lift readFrom' 
    modify (innerExpr:) 
    lift $ modify (drop 1) -- this seems to be missing from the Python 

हास्केल में, एक सूची के अंत में जोड़कर अक्षम है, तो मैं बजाय prepended, और फिर बाद में सूची को उलट दिया। यदि आप प्रदर्शन में रूचि रखते हैं, तो बेहतर सूची-जैसी डेटा संरचनाएं आप उपयोग कर सकते हैं।

यहाँ पूरी फाइल है: http://hpaste.org/77852

---

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