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解析器组合器 - 字符串函数

回答

相关问题