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 つしかないバージョンであっても、保守的にコンパイルを拒否します。

いくつかの標準的な修正があります。

  1. 型シグネチャを指定して他の型を修正し、コンパイラにどのインスタンスを選択するかを伝えます。残念ながら、この解決策はうまくいきません。あなたの typeclass-polymorphic 値sId :: FAState a b => a -> Intは、型変数aとbその型の両方を言及していません。この値を使用することは決してできないため、最近の GHC はこの型クラスを少し前に (インスタンスを作成したり、クラス メソッドを呼び出そうとする前に) 拒否すると思いますが、現時点でテストするために横たわっているものはありません.

    このソリューションの例を示すために、sTransitions代わりに を検討しsIdてください。(より原則的で一般化可能な変換では、メソッドにのみ型シグネチャが与えられます。たとえば、 からへの変換を簡単に一般化できます。)sTransitions nfasTransitions nfa :: Transitions Symbol NFAsTransitions 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

    これは2つのことを行います.1つ目は, を知っていれaば, をまだ知らない場合でもこれを使用してインスタンスを選択できることbをGHCに伝えます.つまり、2 つのインスタンスが同じ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 が 2 番目の変数について十分に認識していないと不平を言っている場合は、まあ... 2 番目の変数のすべてのインスタンス化は (いくつかの等式制約までは) 等しく適切であるといつでも伝えることができます。例えば：

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

    は~型レベルの等価性に対する GHC の表記法です。これが機能する方法は非常に卑劣であり、他の場所でよく説明されています (本当に必要な場合は、いくつかのリンクを掘り下げます) が、説明の短いバージョンは、これが GHC に、十分に知っている場合NFAは最初に選択することを伝えることです変数の場合、このインスタンスにすぐにコミットでき、コミットされた後にのみ、2 番目の引数が実際に であることを再確認しSymbolます。

楽しみ！

于 2012-08-31T19:03:25.613 に答える