5

私は論文 ( 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) = ???????
4

2 に答える 2

4

まったく同じ問題があり、data-reify を使用して解決策を見つけました。

1. EDSL にはリストがありませんが、グラフ タイプにはリストが含まれている可能性があります。 2. 異なるタイプのデータを同じ結果タイプに具体化することができます。

そのため、結果の型にリスト コンストラクターを追加することから始めます。

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

次に、Expr a のリストを GraphExpr に具体化する MuRef の 2 番目のインスタンスが必要です。

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

このグラフから具体化されたノード ID のリストを抽出するために、Conses をウォークし、それらからノード ID をリストに抽出する小さな関数を定義できます。

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 のルートは常にコンス ノードになることがわかっているため (リストを具体化するため)、すべてのノード ID が xs にあることがわかっているため、この関数はリストを返します。結果リスト内のすべてのノード ID。

したがって、結果のグラフで walkConses を実行すると、結果が得られます。

[2, 7]

これが役に立てば幸いです。私もこの問題にしばらく取り組んできました。

于 2012-11-21T15:54:36.563 に答える
3

MuRef では実際にそれを行うことはできません。GraphLists には GraphLists は含まれません。ただし、各 Expr を順番に具体化し、1 回限りのコンビネータを記述してそれらを GraphList に分割することができます。

ExprList の内容に対して traverse reifyGraph を使用するだけです。

また、後者は両方ともおそらく newtype である必要があります。

于 2012-07-27T23:21:05.330 に答える