Geek asks and answers

How to restore a list of data using Data.Reify?

I tried to read the document ( http://www.ittc.ku.edu/csdl/fpg/sites/default/files/Gill-09-TypeSafeReification.pdf ) and managed to confirm my symbolic type of expression, but I cannot figure out how restore a list of them. Here's the simplified 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) = ???????
+5
source share
2 answers

I had the same problem and I found a solution using data-reify.

What you need to understand in order to arrive at a solution is the following: 1. Even if the EDSL does not have lists, the type of graph may contain them 2. You can believe different data types into the same type of result.

So, we start by adding list constructors to our result type:

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

MuRef, Expr a GraphExpr.

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

,

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


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

reified node -ids , Conses node -ids .

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

( , IntMap )

, , DAG Cons- node ( ), , node -ids xs node -ids .

, walkConses , :

[2, 7]

, , .

+4

MuRef. GraphLists GraphLists. Expr , GraphList:

reifyGraph ExprList.

, , , .

+3

More articles:


All Articles