class - 我的 Parser 类的类型有什么问题？

Question

这几天比较空闲，所以决定学点haskell。

为了练习，我正在翻译我在 SCALA 的一门类(class)中制作的项目。但是我对这部分代码有疑问。这很容易理解。

这个想法是对一些解析器建模，这些解析器会接受一些字符串并将其解析为包含已解析元素“输出”和“剩余部分”(无法解析的字符串的一部分)的 ParserOutput。

我本可以在不定义新类的情况下完成此操作(仅使用数据“MyParser”)，但我认为定义一个类会很有趣，这样我就可以在一个地方定义我希望解析器工作的所有方法上。

data ParserOutput a = 
    Failure | Success { output :: a, remainder :: String } 
        deriving (Show)

data MyParser t = MyParser (String -> ParserOutput t)

class Parser p where
    parse :: p -> String -> ParserOutput t

instance Parser (MyParser t) where
    parse (MyParser parserDefinition) = parserDefinition

我得到的错误是:

* Couldn't match type `t1' with `t'
      `t1' is a rigid type variable bound by
        the type signature for:
          parse :: forall t1. MyParser t -> String -> ParserOutput t1
        at ...
      `t' is a rigid type variable bound by
        the instance declaration
        at ...
      Expected type: String -> ParserOutput t1
        Actual type: String -> ParserOutput t
    * In the expression: parserDefinition
      In an equation for `parse':
          parse (MyParser parserDefinition) = parserDefinition
      In the instance declaration for `Parser (MyParser t)'
    * Relevant bindings include
        parserDefinition :: String -> ParserOutput t
          (bound at ...)
        parse :: MyParser t -> String -> ParserOutput t1
          (bound at ...)

Answer 1

类型签名

parse :: p -> String -> ParserOutput t

说 parse 可以与调用者选择的任何类型 p 和 t 一起使用。

现在p其实有点受限，因为它必须是Parser的实例，所以有效类型是

parse :: (Parser p) => p -> String -> ParserOutput t

但 t 仍然是完全免费的，与 p 无关。

作为函数的用户，我应该(给定解析器值 px)能够编写例如

( parse px "" :: ParserOutput Int,
  parse px "" :: ParserOutput String,
  parse px "" :: ParserOutput (Double -> Double -> [Bool])
)

再一次，类型签名表明我可以在每次调用中自由地选择 t。

您的 MyParser 实例不满足此要求。为清楚起见，让我们为类型参数使用不同的名称:

instance Parser (MyParser r) where
    parse (MyParser parserDefinition) = parserDefinition

在这种情况下，parse 应该有类型

parse :: MyParser r -> String -> ParserOutput t

但实际的类型是

parse :: MyParser r -> String -> ParserOutput r

parserDefinition 的结果类型直接取决于解析器类型，但 class 声明并未反射(reflect)这一点。

---

如果你真的想为此使用一个类，你需要明确这个关系。

例如，您可以抽象类型构造函数 MyParser，而不是 MyParser t:

class Parser p where
    parse :: p t -> String -> ParserOutput t

instance Parser MyParser where
    parse (MyParser parserDefinition) = parserDefinition

这比您最初的尝试稍微不通用，因为它需要 Parser 实例按其结果类型进行参数化。

要允许任意解析器/结果类型，我们必须使用类似 functional dependencies 的东西:

{-# LANGUAGE FunctionalDependencies, FlexibleInstances #-}

class Parser p t | p -> t where
    parse :: p -> String -> ParserOutput t

instance Parser (MyParser t) t where
    parse (MyParser parserDefinition) = parserDefinition

或使用 associated type families :

{-# LANGUAGE TypeFamilies #-}

class Parser p where
    type Result p
    parse :: p -> String -> ParserOutput (Result p)

instance Parser (MyParser t) where
    type Result (MyParser t) = t
    parse (MyParser parserDefinition) = parserDefinition