Monad Parser - 无法将预期类型“[(b, String)]”与实际类型“Parser b”匹配

Question

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

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))

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

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

Answer 1

>>= return 解析器 b，不是 [(b, String)]。事实上 g v，是 Parser.

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

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)
  )

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

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

Monad Parser - 无法将预期类型“[(b, String)]”与实际类型“Parser b”匹配

Monad Parser - Couldn't match expected type ‘[(b, String)]’ with actual type ‘Parser b’

monads

parsing

haskell

types

functional-programming