parsing - Monad 解析器 - 无法将预期类型 ‘[(b, String)]’ 与实际类型 ‘Parser b’ 匹配

Question

我正在使用 G.Hutton 的“Programming in Haskell”来学习 Haskell。我正在关注 Monadic Parser 的第 13 章。 首先，我定义一个类型解析器:

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

然后是解析函数

parse:: Parser a -> String -> [(a, String)]

我将解析器设为 Monad

instance Monad Parser where
--return :: a -> Parser a
 return v =  P(\inp -> [(v, inp)])

--(>>=) :: Parser a -> (a -> Parser b) -> Parser b
 p >>=  g = P (\inp -> case parse p inp of
  [] -> []
  [(v, out)] -> parse (g v) out)

我的问题出在 Monad 实例的最后一行 为什么会这样

[(v, out)] -> parse (g v) out)

不是这个

[(v, out)] -> (g v))

>>= 返回一个解析器 b，而不是 [(b, String)]。事实上 g v 是一个解析器。

我知道我错了，但我不明白为什么。

Answer 1

>>= 返回一个解析器 b，而不是 [(b, String)]。事实上 g v，是一个 解析器。

这是正确的，但我们正在使用外部 P 构造一个 Parser。确实:

p >>=  g = <b>P</b> (\inp -> case parse p inp of
  [] -> []
  [(v, out)] -> parse (g v) out)

注意P紧跟在=之后。因此，lambda 表达式 \inp -> ... 必须具有 String -> [(b, String)] 类型，而不是 Parser。我们使用 parse 评估解析器，因为它充当“getter”以从 g v 中获取函数。

但是，您的 >>= 实现并不完整。事实上，这是一个回溯解析器，列表可能不包含任何元素(无选项)、一个元素或多个元素。因此，我们应该执行如下映射:

p >>= g = P (
    \inp -> <b>concatMap (\(v, out) -> parse (g v) out)</b> (parse p inp)
  )

或者我们可以使用为列表定义的绑定(bind)运算符>>=:

p >>= g = P (
    \inp -> parse p inp >>= \(v, out) -> parse (g v) out
  )