Intentaré mostrar que esto se puede hacer para GADTs específicos, usando su GADT como ejemplo.
Usaré el paquete Data.Reify. Esto requiere que defina una nueva estructura de datos en la cual las posiciones recusivas son reemplazadas por un parámetro.
data AstNode s where
IntLitN :: Int -> AstNode s
AddN :: s -> s -> AstNode s
BoolLitN :: Bool -> AstNode s
IfThenElseN :: TypeRep -> s -> s -> s -> AstNode s
Tenga en cuenta que elimino mucha información de tipo que estaba disponible en el GADT original. Para los primeros tres constructores, está claro cuál fue el tipo asociado (Int, Int y Bool). Para el último recordaré el tipo usando TypeRep (disponible en Data.Typeable). La instancia para MuRef, requerida por el paquete reify, se muestra a continuación.
instance Typeable e => MuRef (Ast e) where
type DeRef (Ast e) = AstNode
mapDeRef f (IntLit a) = pure $ IntLitN a
mapDeRef f (Add a b) = AddN <$> f a <*> f b
mapDeRef f (BoolLit a) = pure $ BoolLitN a
mapDeRef f (IfThenElse a b c :: Ast e) =
IfThenElseN (typeOf (undefined::e)) <$> f a <*> f b <*> f c
Ahora podemos usar reifyGraph para recuperar compartir. Sin embargo, se perdió mucha información de tipo. Intentemos recuperarlo.Alteré su definición de AST2 ligeramente:
data Ast2 e where
IntLit2 :: Int -> Ast2 Int
Add2 :: Unique -> Unique -> Ast2 Int
BoolLit2 :: Bool -> Ast2 Bool
IfThenElse2 :: Unique -> Unique -> Unique -> Ast2 e
El gráfico del paquete Reify se parece a esto (donde e = AstNode):
data Graph e = Graph [(Unique, e Unique)] Unique
Le permite hacer una nueva estructura de datos del gráfico, donde podemos almacenar Ast2 Int y Ast2 Bool por separado (por lo tanto, donde se ha recuperado la información del tipo):
data Graph2 = Graph2 [(Unique, Ast2 Int)] [(Unique, Ast2 Bool)] Unique
deriving Show
Ahora sólo tenemos que encontrar una función de AstNode Gráfico (el resultado de reifyGraph) a Graph2:
recoverTypes :: Graph AstNode -> Graph2
recoverTypes (Graph xs x) = Graph2 (catMaybes $ map (f toAst2Int) xs)
(catMaybes $ map (f toAst2Bool) xs) x where
f g (u,an) = do a2 <- g an
return (u,a2)
toAst2Int (IntLitN a) = Just $ IntLit2 a
toAst2Int (AddN a b) = Just $ Add2 a b
toAst2Int (IfThenElseN t a b c) | t == typeOf (undefined :: Int)
= Just $ IfThenElse2 a b c
toAst2Int _ = Nothing
toAst2Bool (BoolLitN a) = Just $ BoolLit2 a
toAst2Bool (IfThenElseN t a b c) | t == typeOf (undefined :: Bool)
= Just $ IfThenElse2 a b c
toAst2Bool _ = Nothing
Vamos a hacer un ejemplo:
expr = Add (IntLit 42) expr
test = do
graph <- reifyGraph expr
print graph
print $ recoverTypes graph
Impresiones:
let [(1,AddN 2 1),(2,IntLitN 42)] in 1
Graph2 [(1,Add2 2 1),(2,IntLit2 42)] [] 1
La primera línea nos muestra que reifyGraph ha recuperado correctamente el uso compartido. La segunda línea nos muestra que solo se han encontrado Ast2 Int tipos (que también es correcto).
Este método es fácilmente adaptable para otras GADT específicas, pero no veo cómo podría hacerse completamente genérico.
El código completo se puede encontrar en http://pastebin.com/FwQNMDbs.
Hice mi ejemplo un poco difícil de seguir utilizando los mismos nombres para los constructores de ambos tipos de datos. Los renombré para tener más sentido. Parece que ya hiciste eso en tu código. – tibbe
@ Sjoerd-visscher Creo que la solución (al menos la que usa 'Typeable') tiene un pequeño problema: impide el análisis compartido. No sé si esto se debe al constructor Wrap adicional o debido a algo más. Sin embargo, mi dinero está en el constructor de Wrap. ¿Algunas ideas? –
@AlessandroVermeulen Francamente, no sé nada de compartir. ¿Quién/qué hace el análisis de intercambio? –