5

我正在尝试使用 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

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

4

1 回答 1

7

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

现在，记住这个原则，想想你要求编译器做什么：你已经给出了一个 的实例FAState NFA Symbol，并编写了一个类型类多态的表达式，并且只将第一个类型固定为NFA; 另一个完全打开。编译器可以选择范围内的单个实例（其中另一个变量被单Symbol态FAState NFA Widget为可编译的代码。所以编译器保守地拒绝编译甚至只有一个实例在范围内的版本。

有一些标准修复：

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

    只是举一个这个解决方案的例子，考虑sTransitions而不是sId：这里的类型签名确实提到了这两个变量，所以你可以把 non-compilingsTransitions 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.

享受！

于 2012-08-31T19:03:25.613 回答