haskell - 为什么这个解析器 do-block 会失败？

Question

我试图理解 do-blocks/sequencing Action 、解析器和 monads。

newtype Parser a = P ( String -> [ ( a, String ) ] )

item :: Parser Char
item = P (\inp -> case inp of
             []     -> []
             (x:xs) -> [(x,xs)])

parse :: Parser a -> String -> [(a,String)]
parse (P p) inp = p inp

firstThird :: Parser (Char,Char)
firstThird = do x <- item
                item
                y <- item
                return (x,y)

我不明白为什么

parse firstThird "ab"

评估为

[]

为什么当其中一个 Action 失败时整个 do-block 都失败了？

Answer 1

您还没有包含 Monad您的 Parser 的实例，但标准的可能由以下方式给出:

instance Functor Parser where
  fmap = liftM
instance Applicative Parser where
  pure x = P $ \str -> [(x, str)]
  (<*>) = ap
instance Monad Parser where
  P p >>= f = P $ \str ->
    [result | (x, rest) <- p str, let P q = f x, result <- q rest]

有了这个实例，我可以复制您的结果，并且解析器按预期运行。通常一个单子(monad)解析器被设计成当一个解析器序列被绑定(bind)在一起时(使用 >>= 操作符，或作为 do-block 表示法中的多个步骤)， 打算意思是每个解析器都按顺序尝试，并且必须“成功”才能使整个序列成功。
在您的情况下，“成功”被定义为解析器返回可能解析的非空列表。为了 firstThird返回一个非空列表，三个 item 中的每一个解析器必须按顺序生成一个非空列表。对于输入字符串 "ab" ，第一次调用 item生成非空列表 [('a',"b")] ，第二次调用 item生成非空列表 [('b',"")] , 第三次调用 item没有任何东西可以解析，因此返回空列表 [] .没有其他解析是可能的。
如果您想允许解析器失败但继续解析，您可以使用组合器。有一个标准的名为 optional在 Control.Applicative .
要使用它，您需要一个 Alternative您的 Parser 的实例:

instance Alternative Parser where
  empty = P $ \_ -> []
  P p <|> P q = P $ \str -> p str ++ q str
instance MonadPlus Parser

然后你可以写:

firstThird :: Parser (Char,Char)
firstThird = do x <- item
                optional item
                y <- item
                return (x,y)

这使得:

> parse firstThird "ab"
[(('a','b'),"")]
> parse firstThird "abc"
[(('a','c'),""),(('a','b'),"c")]

请注意 "abc"可以用 firstThird 两种方式解析, 是否跳过中间的解析 item .
这是编写一元解析器的常用方法: Monad用于一系列解析，所有解析都必须成功，而单独的 Alternative (又名 MonadPlus )实例和 <|>运算符特别用于优雅地处理允许解析器失败并允许尝试其他解析器的情况。