多参数类没有实例错误

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会导致代码模糊,将工作,可编译代码转换为非可编码的代码.所以编译器保守地拒绝编译甚至只有一个实例在范围内的版本.

有几个标准修复:

1. 给出一个类型签名来修复另一个类型,告诉编译器选择哪个实例.不幸的是,这个解决方案对你不起作用:你的类型类多态值sId :: FAState a b => a -> Int并没有提到类型变量a和b类型.既然你永远不能使用这个值,我认为现代GHC会稍早拒绝这个类型的类(在你编写任何实例之前或者尝试调用类方法之前),尽管我现在还没有一个人在旁边测试.

   只是举一个这个解决方案的例子,考虑sTransitions而不是sId:这里类型签名确实提到了两个变量,因此你可以将非编译sTransitions nfa转换为yes-compiling 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.

请享用!