如何使用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是否是解决此注释问题的最佳方式？

- ais

---

有趣的问题。我现在没有答案，但是我会分享这个想法。 Free 是归纳的，而 Cofree 是余归纳的。也就是说，使用任意函子的（全）代数来“拆解”（行为良好的）自由单子态是保证终止的，并且使用余代数来“建立”余自由协单态是保证生产力的。反过来则不成立。 - Benjamin Hodgson

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)

- Benjamin Hodgson

---

当你经常遇到这种模式时，直接定义这样一个常量注释就变得非常有用：data (:&) x f a = x :& f a - 当然，这只是一种偏好。 - user2407038

@user2407038 我更喜欢重用像 K 和 :*: 这样的小块，并为特定领域的使用定义类型/模式同义词。 type (x :& g) = K x :*: g 和 pattern x :& y = K x :*: y - Benjamin Hodgson

为什么这个注释原始的Cofree类型不起作用？（或者它可以吗？） - Luciano