haskell - 了解 attoparsec 实现（第 2 部分）

Question

我目前正在努力研究和理解该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

我还不完全理解的是 type-parameter 的用法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其中根本不使用类型参数。我的问题是为什么这个定义是“错误的”以及它会带来什么问题......

Answer 1

attoparsec creates continuation passing style (CPS) parsers and without the forall we wouldn't be able to chain parsers together.

Here is a dramatically simplified version of the the types involved and definition of bindP - the monadic bind operator. We have eliminated the failure continuation and the input source.

{-# 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
                                                  -----
                                                  -----

Notes that Success a r is simply the function type a -> r.

If we replace the definition of runParser with:

runParser :: Success a a -> IResult a

we'll get a type error at the above underlined location. To understand this one can work out the following types:

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

but from the expression (g a) we can also conclude that a has type a which gives us our type error.

Basically Parser a can be thought of as a method (or computation) of generating value of type a and runParser p ks is the way to take that value and feed it to a function which takes an a. The continuation function ks can have type a -> r for any r - the only requirement is that its input type is a. By using Success a a in defining runParser we limit the applicability of runParser to functions of type a -> a. That's why we want to define runParser as:

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

This CPS-style is a very different approach to parsing than what is presented in Monadic Parsing in Haskell

Answer 2