haskell - 了解 attoparsec 实现(第 2 部分)

我目前正在尝试研究和理解 attoparsec 库的源代码，但有一些细节我自己无法弄清楚。例如 Parser 类型的定义:

newtype Parser i a = Parser {
      runParser :: forall r.
                   State i -> Pos -> More
                -> Failure i (State i)   r
                -> Success i (State i) a r
                -> IResult i r
    }

newtype Pos = Pos { fromPos :: Int }
            deriving (Eq, Ord, Show, Num)

data IResult i r =
    Fail i [String] String
  | Partial (i -> IResult i r)
  | Done i r

type Failure i t   r = t -> Pos -> More -> [String] -> String
                       -> IResult i r
type Success i t a r = t -> Pos -> More -> a -> IResult i r

我还没有完全理解类型参数 r 的用法。如果我像这样定义 runParser 的类型签名会有什么不同:
State i -> Pos -> More -> Failure i (State i) a -> Success i (State i) a a -> IResult i a
?

您能否帮助我理解 forall r. 在这种情况下的确切含义以及为什么有必要在 runParser 的类型签名中使用它？

提前很多谢谢!

更新 :进一步澄清我的问题:我目前不明白的是为什么有必要首先引入类型参数 r。可以想象，Parser 类型也可以这样定义:

newtype Parser i a = Parser {
      runParser ::
                   State i -> Pos -> More
                -> Failure i (State i) a
                -> Success i (State i) a
                -> IResult i a
}

data IResult i a =
    Fail i [String] String
    | Partial (i -> IResult i a)
    | Done i a

type Failure i t a  = t -> Pos -> More -> [String] -> String
                      -> IResult i a
type Success i t a = t -> Pos -> More -> a -> IResult i a

其中类型参数 r 根本没有使用。我的问题是为什么这个定义是“错误的”以及它会带来什么问题......

最佳答案

attoparsec 创建连续传递样式 (CPS) 解析器
如果没有 forall 我们将无法链接
解析器在一起。

这是一个大大简化的版本
涉及的类型和 bindP 的定义 - monadic 绑定(bind)运算符。
我们已经消除了故障延续和输入源。

{-# LANGUAGE Rank2Types #-}

type IResult r = r
type Success a r = a -> IResult r  -- Success a r == a -> r

newtype Parser a = Parser {
      runParser :: forall r. Success a r
                -> IResult r
    }

bindP :: Parser a -> (a -> Parser b) -> Parser b
bindP m g =
    Parser $ \ks -> runParser m $ \a -> runParser (g a) ks
                                                  -----
                                                  -----

注意 Success a r 只是函数类型 a -> r 。

如果我们将 runParser 的定义替换为:

runParser :: Success a a -> IResult a

我们将在上面带下划线的位置收到类型错误。
要理解这一点，可以计算出以下类型:

ks                                      :: Success b b
runParser m $ \a -> runParser (g a) ks  :: IResult b
\a -> runParser (g a) ks                :: Success b b  == b -> b
a :: b

但是从表达式 (g a) 我们也可以得出结论，a 的类型是 a这给了我们类型错误。

基本上 Parser a 可以被认为是一种方法(或计算)
生成 a 和 runParser p ks 类型的值的方法是
获取该值并将其提供给采用 a 的函数。
延续函数 ks 可以为任何 a -> r 类型为 r -
唯一的要求是它的输入类型是 a 。
通过在定义 Success a a 时使用 runParser，我们限制了runParser 对 a -> a 类型函数的适用性。这就是为什么我们
想要将 runParser 定义为:

runParser :: Parser a -> (a -> r) -> r

这种 CPS 风格是一种与所呈现的非常不同的解析方法
在 Monadic Parsing in Haskell

关于haskell - 了解 attoparsec 实现(第 2 部分)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27374642/