Wie man eine Liste von Daten mit Data.Reify wieder herstellt?

Question

Ich habe versucht, das Papier zu lesen (http://www.ittc.ku.edu/csdl/fpg/sites/default/files/Gill-09-TypeSafeReification.pdf) und es geschafft, meinen symbolischen Ausdruckstyp zu verifizieren, aber ich kann nicht herausfinden, wie man eine Liste von ihnen wieder herstellt. Hier ist der vereinfachte Code:

{-# OPTIONS_GHC -Wall #-} 
{-# Language TypeOperators #-} 
{-# Language TypeFamilies #-} 
{-# Language FlexibleInstances #-} 

import Control.Applicative 
import Data.Reify 

-- symbolic expression type 
data Expr a = EConst a 
      | EBin (Expr a) (Expr a) 
      deriving Show 

-- corresponding node type 
data GraphExpr a b = GConst a 
        | GBin b b 
        deriving Show 

instance MuRef (Expr a) where 
    type DeRef (Expr a) = GraphExpr a 
    mapDeRef _ (EConst c) = pure (GConst c) 
    mapDeRef f (EBin u v) = GBin <$> f u <*> f v 

-- this works as expected 
main :: IO() 
main = reifyGraph (EBin x (EBin x y)) >>= print 
    where 
    x = EConst "x" 
    y = EConst "y" 
-- (output: "let [(1,GBin 2 3),(3,GBin 2 4),(4,GConst "y"),(2,GConst "x")] in 1") 

-- but what if I want to reify a list of Exprs? 
data ExprList a = ExprList [Expr a] 
data GraphList a b = GraphList [GraphExpr a b] 

instance MuRef (ExprList a) where 
    type DeRef (ExprList a) = GraphList a 
    -- mapDeRef f (ExprList xs) = ??????? 

Answer 1

Sie können das wirklich nicht mit MuRef tun. GraphLists enthalten keine GraphLists. Sie können jedes Expr der Reihe nach wiederholen und einen einmaligen Kombinator schreiben, um sie in Ihre GraphList zu zerlegen:

Verwenden Sie einfach traverse reifyGraph über den Inhalt der ExprList.

Auch sollten beide letzteren wahrscheinlich neu sein.

Answer 2

Ich hatte genau das gleiche Problem, und ich fand eine Lösung mit Daten-Reparatur.

Die Dinge, die Sie zu erkennen, haben zu einer Lösung zu kommen, ist, dass: 1. Auch wenn die EDSL muß nicht-Listen haben, könnte der Diagrammtyp enthält sie 2. Es ist möglich, verschiedene Arten von Daten auf demselben vergegenständlichen Ergebnistyp.

So starten wir durch Hinzufügen Liste Konstrukteuren zu unserem Ergebnistyp:

data GraphExpr a b = GConst a 
        | GBin b b 
        | Cons b b 
        | Nil 
        deriving Show 

Dann brauchen wir eine zweite Instanz von MuRef, die Listen von Expr einer zu GraphExpr verdinglicht.

instance MuRef [Expr a] where 
    type DeRef [Expr a] = GraphExpr a 
    mapDeRef _ [] = pure Nil 
    mapDeRef f (x:xs) = Cons <$> f x <*> f xs 

Jetzt mit dieser an Ort und Stelle, wenn wir versuchen, eine Liste Ausdruck vergegenständlichen

reified = reifyGraph [EBin x (EBin x y), Ebin y (EBin x y)] 
       where x = EConst "x" 
        y = EConst "y" 

Wir werden das Ergebnis

erhalten

let [(1,Cons 2 6),(6,Cons 7 9),(9,Nil),(7,GBin 5 8),(8,GBin 3 5),(2,GBin 3 4),(4,GBin 3 5),(5,GConst "y"),(3,GConst "x")] in 1 

Um die Liste der verdinglichten Knoten-IDs zu extrahieren Aus diesem Graphen können wir eine kleine Funktion definieren, um die Conses zu durchlaufen und die Node-IDs daraus in eine Liste zu extrahieren.

walkConses :: Graph (GraphExpr t) -> [Unique] 
walkConses (Graph xs root) = go (lookup root xs) 
where 
    go (Just (Cons n1 n2)) = n1 : go (lookup n2 xs) 
    go (Just Nil) = [] 

(Wenn die Graphen riesig sind, könnte es eine gute Idee sein, sie vor dem Beginn der Wanderung zu einem IntMap zu konvertieren)

wie eine Teilfunktion Das sieht, aber da wir wissen, dass die Wurzel Die DAG wird immer ein Cons-Knoten sein (da wir eine Liste neu erstellen), und da wir wissen, dass alle Knoten-IDs in xs sind, gibt diese Funktion eine Liste aller Knoten-IDs in der Ergebnisliste zurück.

Wenn wir also walkConses auf unserer resultierende Graph führen wir das Ergebnis bekommen:

[2, 7] 

hoffte, das hilft, ich habe auch eine Weile mit diesem Problem gerungen.