我的解析器 class 的类型有什么问题？

Question

这几天有点空闲所以决定学点东西haskell。

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

我们的想法是对一些解析器建模，这些解析器会接受一些字符串并将其解析为包含已解析元素 "output" 和 "remainder"（无法解析的字符串的一部分）的 ParserOutput被解析）。

我可以在不定义新的 class 的情况下完成此操作（仅使用数据 "MyParser"），但我认为定义一个 class 会很有趣，这样我就可以定义在一个地方，我希望解析器可以处理的所有方法。

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 声明并未反映这一点。

如果你真的想为此使用 class，你需要明确这种关系。

例如，您可以抽象类型构造函数 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

我的解析器 class 的类型有什么问题？

What's wrong with the types for my Parser class?

haskell

class

instance