haskell - 多参数类没有实例错误

Question

我正在尝试使用 Haskell 编写一个基本的词法分析器。为了实现 DFA 和 NFA，我决定将一些常用函数放入 FA 和 FAState 类中。

-- |A class for defining the common functionality of all finite automatons.
class FA a b where
    mutateId :: a -> Int -> a               -- ^Returns a new FA by changing the sId of the input FA.
    mutateType :: a -> StateType -> a       -- ^Returns a new FA by changing the stateType of the input FA.
    addTransition :: a -> (b, a) -> a       -- ^Returns a new FA by adding a new transition to the input FA.


-- |A class for defining the common functionality of all finite automaton states.
class FA a b => FAState a b where
    sId :: a -> Int                         -- ^An unique identifier for the state(hence the prefix s).
    sType :: a -> StateType                 -- ^The type of the state.
    sTransitions :: a -> Transitions b a    -- ^The transitions that occur from this state.

在哪里，

-- |A type which identifies different types of a FA state.
data StateType = Start | Normal | Final
    deriving (Show, Read, Eq)

-- |A type which represents a list of transitions on input a to b.
-- Eg. [(Char, DFA)] represents the transition on a Char input.
type Transitions a b = [(a, b)]

因此，b 表示发生转换的数据类型。对于 DFA，b = Char，而对于 NFA，b = Symbol。

data Symbol = Alphabet Char | Epsilon
    deriving (Show, Read, Eq) 

DFA和NFA分别定义为:

data DFA = DState Int StateType (Transitions Char DFA)
    deriving (Show, Read)
data NFA = NState Int StateType (Transitions Symbol NFA)
    deriving (Show, Read)

我对 FA 和 FAState 的实例定义有疑问:

instance FA DFA Char where
    mutateId (DState i ty ts) new_i = DState new_i ty ts
    mutateType (DState i ty ts) new_ty = DState i new_ty ts
    addTransition (DState i ty ts) state = DState i ty (state:ts)

instance FAState DFA Char where
    sId (DState i t ts) = i
    sType (DState i t ts) = t
    sTransitions (DState i t ts) = ts

instance FA NFA Symbol where
    mutateId (NState i ty ts) new_i = NState new_i ty ts
    mutateType (NState i ty ts) new_ty = NState i new_ty ts
    addTransition (NState i ty ts) state = NState i ty (state:ts)

instance FAState NFA Symbol where
    sId (NState i t ts) = i
    sType (NState i t ts) = t
    sTransitions (NState i t ts) = ts

在尝试运行任何函数时，我得到一个无实例错误:

>>sId egNFA

<interactive>:15:1:
    No instance for (FAState NFA b0)
      arising from a use of `sId'
    Possible fix: add an instance declaration for (FAState NFA b0)
    In the expression: sId egNFA
    In an equation for `it': it = sId egNFA

我不明白这里发生了什么。

Answer 1

您的问题的根源是:实例调度永远不会使推断的类型更具体，即使这将允许它选择一个实例。这个设计决策与所谓的“开放世界”类模型有关:目标是代码的行为(包括“是否编译”)永远不应该仅仅通过添加类型类的实例而改变。

现在，记住这个原则，想想你要求编译器做什么:你已经给出了 FAState NFA Symbol 的实例。 ，并编写了一个类型类多态的表达式，并且仅将第一个类型固定为 NFA ;另一个完全打开。编译器可以选择范围内的单个实例(其中另一个变量被单形为 Symbol )，但这会违反我们的设计原则:现在为(比如说)FAState NFA Widget 添加一个实例会导致模棱两可的代码，将工作的、可编译的代码变成不可编译的代码。所以编译器保守地拒绝编译甚至只有一个实例在范围内的版本。

有一些标准修复:

给出一个类型签名来修复其他类型，告诉编译器选择哪个实例。不幸的是，这个解决方案对你不起作用:你的 typeclass-polymorphic 值 sId :: FAState a b => a -> Int没有提到两个类型变量 a和 b在它的类型中。由于你永远不能使用这个值，我认为现代 GHC 会更早地拒绝这个类型类(在你编写任何实例或尝试调用类方法之前)，尽管我目前还没有一个可以测试.

仅举一个此解决方案的示例，请考虑 sTransitions而不是 sId :这里的类型签名确实提到了这两个变量，所以你可以把非编译 sTransitions nfa进入是编译sTransitions nfa :: Transitions Symbol NFA . (更原则性、可概括的转换仅给出方法的类型签名；例如，您可以轻松概括从 sTransitions nfa 到 (sTransitions :: NFA -> Transitions Symbol NFA) dfa 的转换。)

使用函数依赖项。这里的想法是状态的类型完全由自动机的类型决定，所以从道德上讲，只需修复类中的第一个类型变量就足够了。告诉 GHC 这个事实的语法如下所示:

class FAState a b | a -> b where
    {- ...same as before -}
-- instance declarations look the same as before, too

这做了两件事:首先，它告诉 GHC 如果它知道 a ，它可以使用它来选择一个实例，即使它还不知道 b ，其次，它告诉 GHC 仔细检查类的任何一对实例是否违反了功能约束，也就是说，没有两个实例具有相同的 a。但不同b .

使用(关联的)类型族。这与前面的想法相同，但可能以更熟悉的范式表达。这个语法看起来像这样:

class FAState a where
    type State a
    sId :: a -> Int
    sType :: a -> StateType
    sTransitions :: a -> Transitions (State a) a

instance FAState NFA where
    type State NFA = Symbol
    -- methods are the same as before

这引入了一个名为 State 的新类型构造函数。 (您可以在类型签名等中使用)。您可以将其视为类型级别的函数，将类型作为输入类型，这些类型是类 FAState 的实例并输出与该类型自动机相关的状态类型。

使您的实例声明更具多态性。如果 GHC 提示它对第二个变量知之甚少，那么……您总是可以告诉它第二个变量的所有实例都同样好(直到某些等式约束)。例如:

-- class definition same as before
instance b ~ Symbol => FAState NFA b where
    -- methods same as before

~是 GHC 的类型级别相等表示法。它的工作方式非常隐蔽，并且在其他地方都有很好的描述(如果你真的想要它们，我会挖掘一些链接)，但简短的解释是这告诉 GHC 如果它知道足够的信息来选择 NFA作为第一个变量，它可以立即提交到这个实例，只有在提交之后，它才会仔细检查第二个参数是否实际上是 Symbol .

享受!