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

Question

这些天我一直有一些空闲时间，所以我决定学习一些haskell。

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

这个想法是为一些解析器建模，该解析器将使用一些字符串，并将其解析为一个包含解析元素“ output”和“ remainder”（无法解析的字符串的一部分）的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

我得到的错误是：

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

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实例不满足此要求。为了清楚起见，让我们对type参数使用其他名称：

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

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

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

但实际类型是

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

随着parserDefinition结果类型直接取决于解析器类型，但class声明并没有反映这一点。

如果您确实想为此使用类，则需要使此关系明确。

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

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

instance Parser MyParser where
    parse (MyParser parserDefinition) = parserDefinition

这与您最初的尝试相比不太通用，因为它需要根据Parser实例的结果类型对其进行参数化。

为了允许任意的解析器/结果类型，我们必须使用类似函数依赖的东西：

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

或使用关联的类型族：

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