Kein Fehler mit mehreren Parameterklassen

Question

Ich versuche, einen grundlegenden Lexer mit Haskell zu schreiben. Für die Umsetzung des EDA und des NFA habe ich beschlossen, einige allgemeine Funktionen in die Klassen FA und FAState zu integrieren.

-- |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. 

wo

-- |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)] 

Daher stellt B den Datentyp, für die Übergänge auftreten. Für ein DFA ist b = Char, während für ein NFA b = Symbol ist.

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

DFA und NFA sind jeweils wie folgt definiert:

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

Ich bin ein Problem mit den Instanzdefinitionen von FA & FAState mit: von laufen

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 

Beim Versuch irgend die Funktionen bekomme ich einen keine Instanz Fehler:

>>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 

Ich verstehe nicht, was hier passiert.

Answer 1

Die Wurzel Ihres Problems ist dies: Instanzversand wird nie einen abgeleiteten Typ spezifischer machen, auch wenn das erlauben würde, eine Instanz zu wählen. Diese Design-Entscheidung bezieht sich auf das sogenannte "Open-World" -Modell von Klassen: Das Ziel ist, dass sich das Code-Verhalten (einschließlich "ob es kompiliert") niemals ändert, nur indem Instanzen einer Typklasse hinzugefügt werden.

Nun, das Prinzip im Auge behalten, darüber nachzudenken, was Sie den Compiler gefragt haben zu tun: Sie eine Instanz von FAState NFA Symbol gegeben haben, und einen Ausdruck geschrieben, die polymorph und typeclass behebt nur die erste Art zu NFA; der andere ist völlig offen gelassen. Der Compiler könnte wählen Sie die einzelne Instanz, die im Bereich ist (wo die andere Variable ist monomorphed zu Symbol), aber dies würde unser Design-Prinzip verletzen: jetzt Hinzufügen einer Instanz für (sagen) FAState NFA Widget würde in mehrdeutigen Code, drehen arbeiten, kompilierbar Code in nicht kompilierbaren Code. Daher lehnt der Compiler es konservativ ab, selbst die Version mit nur einer Instanz im Gültigkeitsbereich zu kompilieren.

Es gibt ein paar Standard-Korrekturen:

1. eine Art Unterschrift Geben Sie die andere Art zu beheben, den Compiler zu sagen, die Instanz zu wählen. Leider funktioniert diese Lösung nicht für Sie: Ihr Typklassen-polymorpher Wert sId :: FAState a b => a -> Int erwähnt in ihrem Typ nicht beide Typvariablen a und b. Da Sie diesen Wert niemals verwenden können, denke ich, dass moderne GHCs diese Typklasse etwas früher ablehnen werden (bevor Sie überhaupt Instanzen schreiben oder versuchen, die Klassenmethoden aufzurufen), obwohl ich momentan nicht einen herumliegen habe, um ihn zu testen .

   Nur ein Beispiel für diese Lösung zu geben, betrachten sTransitions statt sId: hier die Art Unterschrift beider Variablen nicht erwähnt, so dass Sie die nicht-Kompilierung sTransitions nfa in dem Ja-Kompilierung sTransitions nfa :: Transitions Symbol NFA drehen können. (Die prinzipielle verallgemeinerbare Transformation gibt nur eine Typ-Signatur für die Methode; z. B. können Sie die Übersetzung leicht von sTransitions nfa zu (sTransitions :: NFA -> Transitions Symbol NFA) dfa verallgemeinern.)

2. Verwenden Sie Funktionsabhängigkeiten. Die Idee hier ist, dass der Typ des Zustands vollständig durch den Typ des Automaten bestimmt wird, also moralisch sollte es ausreichen, nur die erste Typvariable in der Klasse zu reparieren. Die Syntax, die GHC über diese Tatsache erzählt sieht wie folgt aus:

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

   Dies macht zwei Dinge: Erstens, es sagt GHC, dass, wenn es a weiß, ist es diese verwenden können, um eine Instanz zu wählen, auch wenn es noch nicht wissen b, und zweitens teilt es GHC, um zu überprüfen, dass kein Paar Instanzen der Klasse die Funktionalität Einschränkung verletzen, das heißt, keine zwei Instanzen haben die gleiche a aber andere b.

3. Verwenden Sie (zugeordnete) Typfamilien. Dies ist die gleiche Idee wie die vorherige, aber in einem vielleicht bekannteren Paradigma ausgedrückt. Die Syntax für diese sieht wie folgt aus:

   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 
   

   Dies stellt einen neuen Typkonstruktor namens State (die Sie in Art Signaturen usw. verwenden können). Sie können es sich als eine Funktion auf der Typenebene vorstellen, die als Eingabetypen Instanzen der Klasse FAState verwendet und den Typ des diesem Automatentyp zugeordneten Zustands ausgibt.

4. Machen Sie Ihre Instanzdeklarationen polymorpher. Wenn GHC sich beschwert, dass es nicht genug über die zweite Variable weiß, naja ... Sie können ihm immer sagen, dass alle Instanziierungen der zweiten Variablen gleich gut sind (bis zu einigen Gleichheitsbedingungen). Zum Beispiel:

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

   Die ~ ist Schreibweise des GHC für Typ-Ebene Gleichheit. Die Art und Weise, wie dies funktioniert, ist ziemlich hinterhältig und wird an anderer Stelle gut beschrieben (ich werde einige Links ausgraben, wenn Sie sie wirklich wollen), aber die kurze Version der Erklärung ist, dass dies GHC sagt, wenn es genug weiß, um NFA zu wählen erste Variable, dann kann sie sofort an diese Instanz übergeben werden, und erst nachdem sie festgeschrieben wurde, prüft sie, ob das zweite Argument tatsächlich Symbol ist.

Genießen Sie!