多参数类没有实例错误

Question

我想用Haskell写一个基本的词法分析器。为了实现DFA和NFA，我决定将一些常用函数放入FA和FAS类。

-- |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 =符号。

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添加一个实例会导致模糊的代码，从而导致工作，可编译编码成不可编译的代码。所以编译器保守地拒绝编译即使只有一个实例在范围内的版本。

有几个标准的修正：

1. 给一个类型签名，以确定其它类型告诉编译器选择哪一个实例。不幸的是，这个解决方案不适合你：你的类型类型多态值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。）

2. 使用函数依赖关系。这里的想法是，状态的类型完全由自动机的类型决定，所以在道德上它应该足以修正类中的第一个类型变量。告诉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。

3. 使用（关联）类型系列。这与之前的想法是一样的，但也许是一种更为熟悉的范式。这一个语法如下：

   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类别的实例的输入类型，并输出与该类型自动机相关的状态类型。

4. 使您的实例声明更具多态性。如果GHC抱怨说它对第二个变量的了解不够，那么......你总是可以告诉它，第二个变量的所有实例都是同样好的（达到一些等式约束）。例如：

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

   ~是GHC对于类型级别相等的表示法。这种方式的工作方式非常鬼鬼祟祟，在其他地方也有很好的描述（如果你真的想要他们，我会挖掘一些链接），但是这个解释的简短版本是这告诉GHC，如果它足够了解NFA作为第一个变量，那么它可以立即提交给这个实例，并且只有在它提交之后才会再次检查第二个参数实际上是Symbol。

享受！