存在量化解析器的类型签名

Question

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

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

我在左侧使用其中一个表示错误消息，在右侧使用解析表达式和其余标记。

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

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

我的目标是使解析器更加通用，使其不仅将令牌作为输入。所以我使用了pragma并将其更改为：

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

我想知道的是：“parse”函数现在有什么类型？

我无法弄清楚，也无法推断。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中）中看到过这种情况。但我现在看到，这只是将字符串作为输入的解析器的简写。

使用“数据解析器b a”是有意义的，这是我之前也尝试过的，但是后来我在解析器的monad实例中出现了一个奇怪的错误，因为我写了数据解析器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)

如果您使用解析器b a而不是解析器a b，为什么它会工作？为什么在解析器中需要这个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

i、 e.构造器解析器是一个普遍量化的函数，采用a（[b]-

具体来说：parse与Parser相反；它交换了量子数，所以它是一个存在函数

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

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

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

在这一点上，很明显你不能以任何有意义的方式使用它：所有b.[b]的[]和未定义的（正如蒂肯·耶尔维斯所说，[undefined]，[undefined，undefined]，[undefined，undefined，undefined]等）。

我不确定你到底打算用这种类型做什么，但存在主义绝对不是正确的方法。也许你应该这么做

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