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を破棄することができます。

compileE :: Expr -> Prog 
compileE = cata compile_ 

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