如何使用Data.Reify具体化数据列表？

Question

我试着阅读论文(http://www.ittc.ku.edu/csdl/fpg/sites/default/files/Gill-09-TypeSafeReification.pdf)并设法具体化我的符号表达式类型，但我不知道如何具体化它们的列表。下面是简化的代码：

{-# 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

我遇到了完全相同的问题，我找到了一个使用data-reify的解决方案。

要得到解决方案，你必须意识到的事情是: 1.即使EDSL没有列表，图形类型也可以包含它们2.可以将不同类型的数据具体化为相同的结果类型。

因此，我们首先将列表构造函数添加到结果类型中：

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

为了从这个图中提取实例化的node-id列表，我们可以定义一个小函数来遍历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- in都在X中，所以这个函数将返回结果列表中所有node- in的列表。

因此，如果我们在结果图上运行walkConses，我们将得到结果：

[2, 7]

希望这能有所帮助，我也已经在这个问题上挣扎了一段时间了。

Answer 2

你真的不能用MuRef做到这一点。GraphLists不包含GraphLists。您可以依次具体化每个Expr，并编写一个一次性的组合器来将它们嵌入到GraphList中：

只需对ExprList内容使用遍历reifyGraph即可。

另外，后者可能都是新类型。