parsing - 具有存在量化的解析器的类型签名

Question

一开始我有一个简单的解析器类型:

data Parser a = Parser ([Token] -> Either String (a, [Token]))

我在左侧使用Either 作为错误消息，在右侧使用解析表达式和其余的标记。

此函数“解包”解析器函数。

parse :: Parser a -> [Token] -> Either String (a, [Token])
parse (Parser p) = p

我的目标是使解析器更通用，它不仅将标记作为输入。所以我使用了 ExistentialQuantification pragma 并将其更改为:

data Parser a = forall b. ([b] -> Either String (a, [b]))

我想知道的是:函数“解析”现在有什么类型？

我无法弄清楚，也无法推断。 GHCi 给出了这个错误:

Couldn't match type `t' with `[b] -> Either String (t1, [b])'
  `t' is a rigid type variable bound by
    the inferred type of parse :: Parser t1 -> t
    at ParserCombinator.hs:9:1
In the expression: p
In an equation for `parse': parse (Parser p) = p

谢谢你的帮助。

编辑:
非常感谢你的回答。

我希望类型看起来像“Parser a”的原因是因为我在其他解析库中看到过这个，例如在 parsec 中。
但是我现在看到这只是将字符串作为输入的解析器的简写。

使用“data Parser b a”是有意义的这是我之前也尝试过的，但是后来我在解析器的monad实例中出现了一个奇怪的错误，因为我写了 data Parser a b :

import Control.Monad.Error

data Parser a b = Parser ([b] -> Either String (a, [b]))
parse (Parser p) = p

instance Monad (Parser x) where
    p >>= f = Parser (\tokens -> do
        (parsed, rest) <- parse p tokens 
        parse (f parsed) rest)
    return a = Parser (\ts -> Right (a, ts))
    fail b     = Parser (\_ -> Left b)

它给出了这个错误:

ParserCombinator.hs:12:18:
    Couldn't match type `x' with `b'
      `x' is a rigid type variable bound by
          the instance declaration at ParserCombinator.hs:9:24
      `b' is a rigid type variable bound by
          the type signature for
            >>= :: Parser x a -> (a -> Parser x b) -> Parser x b
          at ParserCombinator.hs:10:5
    Expected type: a
      Actual type: x
    In the first argument of `f', namely `parsed'
    In the first argument of `parse', namely `(f parsed)'
    In a stmt of a 'do' block: parse (f parsed) rest

ParserCombinator.hs:12:26:
    Couldn't match type `a' with `b'
      `a' is a rigid type variable bound by
          the type signature for
            >>= :: Parser x a -> (a -> Parser x b) -> Parser x b
          at ParserCombinator.hs:10:5
      `b' is a rigid type variable bound by
          the type signature for
            >>= :: Parser x a -> (a -> Parser x b) -> Parser x b
          at ParserCombinator.hs:10:5
    Expected type: [b]
      Actual type: [a]
    In the second argument of `parse', namely `rest'
    In a stmt of a 'do' block: parse (f parsed) rest

ParserCombinator.hs:13:38:
    Couldn't match type `a' with `x'
      `a' is a rigid type variable bound by
          the type signature for return :: a -> Parser x a
          at ParserCombinator.hs:13:5
      `x' is a rigid type variable bound by
          the instance declaration at ParserCombinator.hs:9:24
    In the expression: a
    In the first argument of `Right', namely `(a, ts)'
    In the expression: Right (a, ts)

为什么使用 Parser b a 而不是 Parser a b 会起作用？为什么我在解析器 x 中需要这个 x？它包含什么？
如果您可以为另一个使用此变量的 monad 实例举一个例子，那就太好了。

Answer 1

你的意思是

data Parser a = forall b. Parser ([b] -> Either String (a, [b]))

如果你用更严格的 GADT 符号来写存在词，这实际上意味着什么会变得更清楚:

data Parser a where
  Parser :: forall b. ([b] -> Either String (a, [b])) -> Parser a

即构造函数 Parser是一个普遍量化的函数，采用 ([b] -> ...解析器，但总是返回 Parser a那不知 Prop 体是什么b是要在里面使用。因此，这基本上是无用的:您不能提供 b 的列表。如果您不知道实际应该是什么类型的 token !

具体来说:parse将是 Parser 的倒数;交换量词，因此它是一个存在(duh)函数

parse :: exists b . Parser a -> ([b] -> Either String (a, [b]))

现在，Haskell 中不存在这样的类型，但它相当于具有通用参数:

parse :: Parser a -> ((forall b . [b]) -> Either String (a, exists b . [b]))

在这一点上，很明显你不能以任何有意义的方式使用它:forall b. [b] 的唯一居民。是 []和 undefined (并且，正如吉洪杰尔维斯所说， [undefined] 、 [undefined, undefined] 、 [undefined, undefined, undefined] 等)。

我不确定您实际上打算用这种类型做什么，但是存在主义绝对不是正确的方法。可能你应该这样做

data Parser b a = Parser ([b] -> Either String (a, [b]))