Haskell 解析器组合器 - 字符串函数

Question

我一直在阅读有关解析器组合器的教程，我遇到了一个函数，我想在尝试理解它时得到一些帮助。

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 的操作，它将 return [].

我的问题是它是如何失败的？当 char c return 是一个空列表时会发生什么？

Answer 1

假设您的 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) }

首先，让我们对其进行脱糖：

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 没有任何工作要做，因为列表是空的！因此，从那时起对 >>= 的任何调用都只会遇到一个空列表并将其传递。

引用透明性的一个美妙之处在于，您可以写下您的表达式并通过替换定义和手动执行函数应用来计算它。

Haskell 解析器组合器 - 字符串函数

Haskell Parser Combinators - String function

parsing

haskell

parser-combinators