No hay error de instancia con las clases de parámetros múltiples

Question

Estoy intentando escribir un lector de letras básico usando Haskell. Para implementar DFA y NFA, decidí poner algunas funciones comunes en las clases FA y 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. 

donde,

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

Por lo tanto, B representa el tipo de datos para el que se producen las transiciones. Para un DFA, b = Char, mientras que para un NFA, b = Símbolo.

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

DFA y NFA se definen respectivamente como:

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

Estoy teniendo un problema con las definiciones de instancia de 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 

Al intentar ejecutar cualquiera de las funciones obtengo un error sin instancia:

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

No entiendo qué está pasando aquí.

Answer 1

La raíz del problema es la siguiente: ejemplo de despacho será Nunca hacer un tipo inferido más específico, incluso si eso sería permitir que se elija una instancia. Esta decisión de diseño está relacionada con el llamado modelo de clases de "mundo abierto": el objetivo es que el comportamiento del código (incluido "si compila") nunca debería cambiar simplemente agregando instancias de una clase de tipos.

Ahora, manteniendo ese principio en mente, piensa en lo que has pedido el compilador para hacer: usted ha dado una instancia de FAState NFA Symbol, y se escribe una expresión que es clase de tipos polimórficos y sólo se fija el primer tipo deNFA; el otro queda completamente abierto. El compilador podría elegir la instancia única que está en su alcance (en el que la otra variable se monomorphed a Symbol), pero esto violaría nuestro principio de diseño: ahora la adición de una instancia de (digamos) FAState NFA Widget daría lugar a ambigüedad en el código, convirtiendo de trabajo, compilables código en código no compilable. Así que el compilador se rehúsa conservadoramente a compilar incluso la versión con solo una instancia en el alcance.

Hay algunas correcciones estándar:

1. Dar un tipo de firma para fijar el otro tipo, diciéndole al compilador qué instancia para elegir. Desafortunadamente, esta solución no funcionará para usted: su valor polimórfico typeclass sId :: FAState a b => a -> Int no menciona las dos variables de tipo a y b en su tipo. Como nunca puedes usar este valor, creo que los GHC modernos rechazarán esta clase de tipos un poco antes (incluso antes de que escribas instancias o intentes invocar los métodos de la clase), aunque no tengo ninguno para probar en este momento. .

   Sólo para dar un ejemplo de esta solución, en lugar de considerar sTransitionssId: aquí el tipo de firma menciona ambas variables, lo que puede convertir la sTransitions nfa no compilar en el sí-compilar sTransitions nfa :: Transitions Symbol NFA. (La transformación más generalizable y generalizable proporciona una firma de tipo solo en el método, por ejemplo, puede generalizar fácilmente la traducción de sTransitions nfa a (sTransitions :: NFA -> Transitions Symbol NFA) dfa.)

2. Utilice dependencias de funciones. La idea aquí es que el tipo de estado está completamente determinado por el tipo de autómata, por lo que, moralmente, debería ser suficiente para fijar la primera variable de tipo en la clase. La sintaxis que dice GHC acerca de este hecho es el siguiente:

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

   Esto hace dos cosas: en primer lugar, le dice GHC que si se sabe a, se puede usar esto para elegir una instancia incluso si no lo hace todavía saber b, y segundo, le dice a GHC que verifique que ningún par de instancias de la clase viole la restricción de funcionalidad, es decir, que no hay dos instancias que tengan el mismo a pero diferente b.

3. Usar familias de tipo (asociado). Esta es la misma idea que la anterior, pero expresada en un paradigma quizás más familiar. La sintaxis para esto es el siguiente:

   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 
   

   Esto introduce un nuevo tipo constructor llamado State (que se puede utilizar en las firmas de tipos y así sucesivamente). Puede considerarlo como una función en el nivel de tipo que toma como tipos de entradas que son instancias de la clase FAState y emite el tipo del estado asociado con ese tipo de autómata.

4. Haga que sus declaraciones de instancia sean más polimórficas. Si GHC se queja de que no sabe lo suficiente sobre la segunda variable, bueno ... siempre se puede decir que todas las instancias de la segunda variable son igualmente buenas (hasta algunas restricciones de igualdad). Por ejemplo:

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

   El ~ es la notación de GHC por la igualdad de nivel tipo. La forma en que esto funciona es bastante furtiva, y está bien descrita en otro lugar (voy a buscar algunos enlaces si realmente los quieres), pero la versión corta de la explicación es que esto le dice a GHC que si sabe lo suficiente como para elegir NFA como primera variable, entonces puede comprometerse con esta instancia de inmediato, y solo después de que se haya confirmado, comprueba dos veces que el segundo argumento es en realidad Symbol.

Enjoy!