Wie kann ich die Freigabe in einem GADT wiederherstellen?

Question

In Type-Safe Observable Sharing in Haskell Andy Gill zeigt, wie die Freigabe, die auf dem Haskell-Ebene existiert, in einem DSL wiederherzustellen. Seine Lösung ist in der data-reify package implementiert. Kann dieser Ansatz geändert werden, um mit GADTs zu arbeiten? Zum Beispiel diese GADT gegeben:

data Ast e where 
    IntLit :: Int -> Ast Int 
    Add :: Ast Int -> Ast Int -> Ast Int 
    BoolLit :: Bool -> Ast Bool 
    IfThenElse :: Ast Bool -> Ast e -> Ast e -> Ast e 

Ich mag würde Sharing wiederherzustellen, indem die oben AST

type Name = Unique 

data Ast2 e where 
    IntLit2 :: Int -> Ast2 Int 
    Add2 :: Ast2 Int -> Ast2 Int -> Ast2 Int 
    BoolLit2 :: Bool -> Ast2 Bool 
    IfThenElse2 :: Ast2 Bool -> Ast2 e -> Ast2 e -> Ast2 e 
    Var :: Name -> Ast2 e 

durch die Art und Weise einer Funktion Umwandlung

recoverSharing :: Ast -> (Map Name, Ast2 e1, Ast2 e2) 

(I‘ Ich bin mir nicht sicher über den Typ von recoverSharing.)

Beachten Sie, dass ich keine neuen Bindins vorstellen möchte gs über ein let-Konstrukt, aber nur bei der Wiederherstellung der Freigabe, die auf der Haskell-Ebene existierte. Deshalb habe ich recoverSharing eine Map zurückgeben.

Wenn es nicht als wiederverwendbares Paket getan werden kann, kann es zumindest für bestimmte GADT getan werden?

Answer 1

Interessantes Puzzle! Es stellt sich heraus, dass Sie Daten mit GADTs replizieren können. Was Sie brauchen, ist ein Wrapper, der den Typ in einem Existenziellen versteckt. Der Typ kann später durch Mustererkennung für den Datentyp Type abgerufen werden.

data Type a where 
    Bool :: Type Bool 
    Int :: Type Int 

data WrappedAst s where 
    Wrap :: Type e -> Ast2 e s -> WrappedAst s 

instance MuRef (Ast e) where 
    type DeRef (Ast e) = WrappedAst 
    mapDeRef f e = Wrap (getType e) <$> mapDeRef' f e 
    where 
     mapDeRef' :: Applicative f => (forall b. (MuRef b, WrappedAst ~ DeRef b) => b -> f u) -> Ast e -> f (Ast2 e u) 
     mapDeRef' f (IntLit i) = pure $ IntLit2 i 
     mapDeRef' f (Add a b) = Add2 <$> (Var Int <$> f a) <*> (Var Int <$> f b) 
     mapDeRef' f (BoolLit b) = pure $ BoolLit2 b 
     mapDeRef' f (IfThenElse b t e) = IfThenElse2 <$> (Var Bool <$> f b) <*> (Var (getType t) <$> f t) <*> (Var (getType e) <$> f e) 

getVar :: Map Name (WrappedAst Name) -> Type e -> Name -> Maybe (Ast2 e Name) 
getVar m t n = case m ! n of Wrap t' e -> (\Refl -> e) <$> typeEq t t' 

Hier ist der gesamte Code: https://gist.github.com/3590197

Edit: Ich mag die Verwendung von Typeable in der anderen Antwort. Also habe ich eine Version meines Codes mit Typeable auch gemacht: https://gist.github.com/3593585. Der Code ist deutlich kürzer. Type e -> wird durch Typeable e => ersetzt, was auch einen Nachteil hat: Wir wissen nicht mehr, dass die möglichen Typen auf Int und Bool beschränkt sind, was bedeutet, dass in IfThenElse eine Einschränkung vorhanden sein muss.

Answer 2

Ich werde versuchen zeigen, dass dies für bestimmte GADTs getan werden kann, mit Ihrem GADT als ein Beispiel.

Ich werde das Data.Reify Paket verwenden. Dazu muss ich eine neue Datenstruktur definieren, in der die rekursiven Positionen durch einen Parameter ersetzt werden.

Beachten Sie, dass ich eine Menge von Typinformationen entfernen, die im ursprünglichen GADT verfügbar waren. Für die ersten drei Konstruktoren ist klar, was der zugehörige Typ war (Int, Int und Bool). Für den letzten werde ich den Typ mit TypeRep erinnern (verfügbar in Data.Typeable). Die für das Paket reeify benötigte Instanz für MuRef ist unten aufgeführt.

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 

Jetzt können wir reifyGraph verwenden Sharing zu erholen. Viele Informationen gingen jedoch verloren. Versuchen wir, es wiederherzustellen.Ich änderte Ihre Definition von AST2 leicht:

data Ast2 e where 
    IntLit2 :: Int -> Ast2 Int 
    Add2 :: Unique -> Unique -> Ast2 Int 
    BoolLit2 :: Bool -> Ast2 Bool 
    IfThenElse2 :: Unique -> Unique -> Unique -> Ast2 e 

Der Graph aus dem reify Paket sieht wie folgt aus (wo e = AstNode):

data Graph e = Graph [(Unique, e Unique)] Unique  

Ermöglicht eine neue Graphdatenstruktur machen, wo Wir können Ast2 Int und Ast2 Bool separat speichern (also, wo die Typinformationen wiederhergestellt wurden):

data Graph2 = Graph2 [(Unique, Ast2 Int)] [(Unique, Ast2 Bool)] Unique 
      deriving Show 

Jetzt müssen wir nur eine Funktion von Graph AstNode (das Ergebnis von reifyGraph) zu Graph2 finden:

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 

wir ein Beispiel tun:

expr = Add (IntLit 42) expr 

test = do 
    graph <- reifyGraph expr 
    print graph 
    print $ recoverTypes graph 

Drucke:

let [(1,AddN 2 1),(2,IntLitN 42)] in 1 
Graph2 [(1,Add2 2 1),(2,IntLit2 42)] [] 1 

Die erste Zeile zeigt uns, dass retifyGraph Freigabe korrekt wiederhergestellt hat. Die zweite Zeile zeigt uns, dass nur Ast2 Int Typen gefunden wurden (was auch korrekt ist).

Diese Methode ist leicht anpassbar für andere spezifische GADTs, aber ich sehe nicht, wie es vollständig generisch gemacht werden könnte.

Der vollständige Code kann unter http://pastebin.com/FwQNMDbs gefunden werden.