cómo analizar cadenas para sintaxis árbol usando GADTs

Question

Estaba leyendo la introducción GADT here y encontré la idea de restringir programador para crear solo el tipo correcto de árbol de sintaxis excelente, y puse esta idea en mi intérprete de cálculo lambda simple, pero más tarde me di cuenta de que no puedo analizar una cadena de este árbol de sintaxis, porque una función de análisis debe devolver diferentes tipos de árbol de sintaxis, dependiendo de la entrada. He aquí un ejemplo:

{-# LANGUAGE GADTs #-} 
data Ident 
data Lambda 
data Application 

data Expr a where 
    Ident :: String -> Expr Ident 
    Lambda :: Expr Ident -> Expr a -> Expr Lambda 
    Application :: Expr a -> Expr a -> Expr Application 

Antes de utilizar GADTs, yo estaba usando esto:

data Expr = Lambda Expr Expr 
      | Ident String 
      | Application Expr Expr 

GADTs son gran ventaja aquí, bacuse ahora no puedo crear árboles de sintaxis no válida como Lambda (Application ..) ...

Pero con GADTs, no pude analizar una cadena y crear un árbol de análisis sintáctico. Aquí están analizador de Lambda, Ident y expresiones de la aplicación:

ident :: Parser (Expr Ident) 
ident = ... 

lambda :: Parser (Expr Lambda) 
lambda = ... 

application :: Parser (Expr Application) 
application = ... 

Ahora el problema es:

expr = choice [ident, application, lambda] 

Obviamente, esto no funciona, ya que cada analizador está regresando diferentes tipos.

Entonces, ¿hay alguna forma de analizar una cadena y crear un árbol de sintaxis con GADT?

Answer 1

Puede usar GADT para hacer un tipo que contenga Expr a para algún desconocido a.

data AnyExpr where AnyExpr :: Expr a -> AnyExpr 

En situaciones en las que No desea restringir Expr a un tipo específico, utilice AnyExpr.

anyExpr :: Parser (Expr a) -> Parser AnyExpr 
anyExpr p = fmap AnyExpr p 

expr :: Parser AnyExpr 
expr = choice [anyExpr ident, anyExpr application, anyExpr lambda]