我有这个简单的Expr
AST,我可以很容易地将其转换为String
。
import Prelude hiding (Foldable)
import qualified Prelude
import Data.Foldable as F
import Data.Functor.Foldable
import Data.Monoid
import Control.Comonad.Cofree
data ExprF r = Const Int
| Add r r
deriving ( Show, Eq, Ord, Functor, Prelude.Foldable )
type Expr = Fix ExprF
testExpr = Fix $ Add (Fix (Const 1)) (Fix (Const 2))
convertToString :: Expr -> String
convertToString = cata $ case
e@(Const x) -> show x
e@(Add x y) -> unwords [x, "+", y]
现在我想添加一个额外的数据到它。所以我正在尝试使用Cofree
type LineNumber = Int
type Expr2 = Cofree ExprF LineNumber
我可以将Expr
转换为Expr2
addLineNumbers :: Expr -> Expr2
addLineNumbers = cata $ case
e@(Const _) -> 1 :< e
e -> 2 :< e
但我不知道如何将Expr2
转换为String
convertToString2 :: Expr2 -> String
convertToString2 = cata $ case
e@(_ :< (Const x)) -> show x
e@(_ :< (Add x y)) -> unwords [x, "+", y]
此外,Cofree是解决这个注释问题的最佳方法吗?
注释语法树的另一种方法是将注释组合到基函子中。
-- constant functor
newtype K c a = K c
deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)
-- functor product
data (f :*: g) a = (:*:) { left :: f a, right :: g a }
deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)
我们将使用函子产品将注释(在K
中)附加到树的每一层。
type AnnExpr = Fix (K LineNumber :*: ExprF)
如果您可以在只检查树的单层时生成注释(也就是说,您的注释生成代码可以表示为自然转换),那么您可以使用以下机器来修改函子,同时保持固定点结构:
hoistFix :: Functor f => (forall a. f a -> g a) -> Fix f -> Fix g
hoistFix f = Fix . f . fmap (hoistFix f) . unFix
不过,这用处有限,因为最有趣的注释(如类型检查)需要遍历语法树。
您可以通过简单地忽略注释来重用代码来拆除Expr
。给出了CCD_ 10的一个代数。。。
-- instructions for a stack machine
data Inst = PUSH Int | ADD
type Prog = [Inst]
compile_ :: ExprF Prog -> Prog
compile_ (Const x) = [PUSH x]
compile_ (Add x y) = x ++ y ++ [ADD]
您可以使用它来拆除Expr
或AnnExpr
:
compileE :: Expr -> Prog
compileE = cata compile_
compileA :: AnnExpr -> Prog
compileA = cata (compile_ . right)