Nessun errore di istanza con classi multiparametro

Question

Sto provando a scrivere un lexer di base usando Haskell. Per l'implementazione di DFA e NFA, ho deciso di inserire alcune funzioni comuni nelle classi FA e 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. 

dove,

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

Quindi, b rappresenta il tipo di dati per cui avvengono le transizioni. Per un DFA, b = Char, mentre per un NFA, b = Symbol.

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

DFA e NFA sono rispettivamente definiti come:

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

Sto avendo un problema con le definizioni di istanza di 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 

Il tentativo di eseguire qualsiasi le funzioni ottengono un errore senza istanze:

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

Non capisco cosa sta succedendo qui.

Answer 1

La radice del problema è la seguente: l'invio di istanza sarà mai rendere un tipo dedotto più specifico, anche se ciò consentirebbe di scegliere un'istanza. Questa decisione di progettazione è legata al cosiddetto modello di classi "open-world": l'obiettivo è che il comportamento del codice (incluso "se compila") non dovrebbe mai cambiare solo aggiungendo istanze di una classe di tipizzazione.

Ora, tenendo questo principio in mente, pensare a quello che hai chiesto il compilatore di fare: hai dato un esempio di FAState NFA Symbol, e scritto un'espressione che è typeclass polimorfa e fissa solo il primo tipo a NFA; l'altro è lasciato completamente aperto. del compilatore potrebbe scegliere l'istanza singola nell'ambito (dove l'altra variabile è monomorfa su Symbol), ma ciò violerebbe il nostro principio di progettazione: ora l'aggiunta di un'istanza per (diciamo) FAState NFA Widget risulterebbe in un codice ambiguo, trasformando il lavoro, compilabile codice in codice non compilabile. Quindi il compilatore rifiuta in modo conservativo di compilare anche la versione con una sola istanza in ambito.

C'è alcune correzioni standard di:

1. Dare una firma tipo per fissare l'altro tipo, dicendo al compilatore quale istanza di scegliere. Sfortunatamente, questa soluzione non funzionerà per te: il tuo valore di polimero tipografico sId :: FAState a b => a -> Int non menziona entrambe le variabili di tipo a e b nel suo tipo. Dal momento che non puoi mai usare questo valore, penso che i moderni GHC respingeranno questa classe di tipo un po 'prima (prima ancora che tu scriva qualche istanza o provi a invocare i metodi della classe), anche se non ne ho uno in giro da testare al momento .

   solo per dare un esempio di questa soluzione, considerano sTransitions invece di sId: qui la firma tipo menziona entrambe le variabili, in modo da poter girare la non compilazione sTransitions nfa nella yes-compilazione sTransitions nfa :: Transitions Symbol NFA. (La trasformazione generalizzata più basata su principi fornisce una firma di tipo solo sul metodo, ad esempio è possibile generalizzare facilmente la traduzione da sTransitions nfa a (sTransitions :: NFA -> Transitions Symbol NFA) dfa.)

2. Utilizzare le dipendenze delle funzioni. L'idea è che il tipo di stato è completamente determinato dal tipo di automa, quindi moralmente dovrebbe essere sufficiente correggere solo la prima variabile di tipo nella classe. La sintassi che racconta GHC su questo fatto si presenta così:

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

   Questo fa due cose: in primo luogo, che racconta GHC che se sa a, si può usare questo per decidere un caso anche se non ha ancora so b, e in secondo luogo, dice a GHC di ricontrollare che nessuna coppia di istanze della classe violano il vincolo di funzionalità, cioè che non esistono due istanze uguali allo a ma diverse b.

3. Utilizzare famiglie di tipi (associati). Questa è la stessa idea della precedente, ma espressa in un paradigma forse più familiare. La sintassi per questo uno si presenta così:

   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 
   

   Questo introduce un nuovo tipo di costruttore di nome State (che è possibile utilizzare in tipo firme e così via). Puoi considerarlo come una funzione a livello di tipo che prende come tipi di input istanze della classe FAState e restituisce il tipo di stato associato a quel tipo di automa.

4. Rendi le dichiarazioni di istanza più polimorfiche. Se il GHC si lamenta di non conoscere abbastanza la seconda variabile, beh ... puoi sempre dire che tutte le istanze della seconda variabile sono ugualmente buone (fino ad alcuni vincoli di uguaglianza). Per esempio:

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

   Il ~ è la notazione di GHC per la parità di tipo di livello. Il modo in cui funziona è piuttosto subdolo, ed è ben descritto altrove (scaverò alcuni link se li vuoi davvero), ma la versione breve della spiegazione è che questo dice a GHC che se ne sa abbastanza da scegliere NFA come prima variabile, quindi può eseguire immediatamente il commit su questa istanza, e solo dopo l'impegno esegue una doppia verifica che il secondo argomento sia effettivamente Symbol.

Divertiti!