haskell - 如何使用带有 Cofree 注释的 AST？

Question

我有这个简单的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 是解决这个注释问题的最好方法吗？

Answer 1

注释语法树的另一种方法是将注释组合到基本仿函数中。

-- 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通过简单地忽略注释。给定 ExprF 的代数...

-- 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)