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] 

이제 추가 데이터를 추가하고 싶습니다. 그래서 나는 Expr

addLineNumbers :: Expr -> Expr2 
addLineNumbers = cata $ \case 
    e@(Const _) -> 1 :< e 
    e -> 2 :< e 

Expr2에하지만 또한 Expr2-String

convertToString2 :: Expr2 -> String 
convertToString2 = cata $ \case 
    e@(_ :< (Const x)) -> show x 
    e@(_ :< (Add x y)) -> unwords [x, "+", y] 

를 변환하는 방법을 알아낼 수 없습니다, Cofree입니다 내가 변환 할 수 있습니다 Cofree

type LineNumber = Int 
type Expr2 = Cofree ExprF LineNumber 

를 사용하는 것을 시도하고있다 이 주석 문제를 해결하는 가장 좋은 방법은 무엇입니까?

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) 

우리는 트리의 각 층의 (a K 내부) 주석을 첨부하는 펑터 제품을 사용하는 것입니다.

type AnnExpr = Fix (K LineNumber :*: ExprF) 

단지 나무의 단일 층 (즉, 귀하의 주석을 창출하는 코드가 자연의 변화로 표현 될 수있다) 당신이를 수정하는 기계의 다음 비트를 사용하여 검사하는 동안은 주석을 생성 할 수있는 경우 장소에 fixpoint 구조를 유지하면서 펑 :

hoistFix :: Functor f => (forall a. f a -> g a) -> Fix f -> Fix g 
hoistFix f = Fix . f . fmap (hoistFix f) . unFix 

를이 같은 유형 검사 한 가장 흥미로운 주석 구문 트리의 탐색을 필요로하지만, 제한된 유용성이다.

코드를 다시 사용하여 주석을 무시함으로써 Expr을 해체 할 수 있습니다.

compileE :: Expr -> Prog 
compileE = cata compile_ 

compileA :: AnnExpr -> Prog 
compileA = cata (compile_ . right)