Monad Parser-无法将预期的类型'[[（b，String）]]'与实际的类型'Parser b'

Question

我正在使用G.Hutton的“在Haskell中编程”来研究Haskell。我正在关注Monadic Parser的ch.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，字符串）]。事实上，g v是Parser。

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

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

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

但是您对>>=的实现未完成。确实，这是一个回溯解析器，列表可能不包含任何元素（没有选项），一个元素或multiple元素。因此，我们应该执行如下映射：

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

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

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