Haskell解析器組合器 - 字符串函數

我一直在閱讀關於解析器組合器的教程，並且我遇到了一個函數，我希望在嘗試理解時有所幫助。Haskell解析器組合器 - 字符串函數

satisfy :: (Char -> Bool) -> Parser Char 
satisfy p = item `bind` \c -> 
    if p c 
    then unit c 
    else (Parser (\cs -> [])) 

char :: Char -> Parser Char 
char c = satisfy (c ==) 

natural :: Parser Integer 
natural = read <$> some (satisfy isDigit) 

string :: String -> Parser String 
string [] = return [] 
string (c:cs) = do { char c; string cs; return (c:cs)}

我的問題是如何做的字符串函數工作或者更確切地說，它是如何終止，說我不喜歡的東西：

let while_parser = string "while"

，然後我用它來解析字符串比方說 parse while_parser "while if"，它會正確解析我的「while」。

但是，如果我嘗試類似parse while_parser "test它將返回[]。

我的問題是它是如何失敗？當char c返回一個空列表時會發生什麼？

來源

2016-08-16 Zubair

我懷疑'char c'不是「返回一個空列表」，而是在輸入結束時失敗*。綁定運算符然後傳播該失敗。 – MathematicalOrchid

你的意思是'讓while_parser = string'而''，對吧？ – sepp2k

@MathematicalOrchid從char滿足的定義中，當char失敗時，它將返回一個生成空列表的函數。傳播失敗是什麼意思？ – Zubair

比方說，你Parser這樣定義：

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

然後你Monad實例可以被定義是這樣的：

instance Monad Parser where 
    return x = Parser $ \input -> [(x, input)] 
    p >>= f = Parser $ \input -> concatMap (\(x,s) -> runParser (f x) s) (runParser p input)

你不知道什麼時候char c在這條線出現故障，會發生什麼代碼：

string (c:cs) = do { char c; string cs; return (c:cs) }

冷杉t，讓我們來解開它：

string (c:cs) = char c >>= \_ -> string cs >>= \_ -> return (c:cs)

現在感興趣的部分是char c >>= \_ -> string cs。根據char的定義和隨後的satisfy的定義，我們看到當char c失敗時，最終runParser (char c) input將評估爲[]。當p是char c時，請看>>=的定義。 concatMap將不會有任何工作要做，因爲列表將爲空！因此，從此之後對>>=的任何調用只會遇到一個空列表並傳遞給它。

有關引用透明度的奇妙之處之一是，您可以寫下表達式並通過替換定義並手動執行函數應用程序來對其進行評估。

來源

2016-08-16 14:55:16 user2297560

從技術上講，它解除了'char c >> string cs >> return（c：cs）'，因爲desugaring與使用的monad無關。 'm >> f'通常是，但不一定要被實現爲'm >> = \ _ - > f'。 – chepner

@chepner是的。我懶得解釋一個切線細節。 – user2297560

謝謝，我想我有種感覺，但遞歸調用字符串適合所有這些？ – Zubair

Haskell解析器組合器 - 字符串函數

回答

相關問題