6

私はこの単純なExprAST を持っており、簡単に に変換できます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 はこの注釈の問題を解決する最良の方法ですか?

4

1 に答える 1

10

構文ツリーに注釈を付ける別の方法は、注釈を基本ファンクターに構成することです。

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

functor プロダクトを使用してK、ツリーの各レイヤーに ( 内に) 注釈を付けます。

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

ツリーの 1 つのレイヤーのみを検査しながら注釈を生成できる場合 (つまり、注釈を生成するコードを自然な変換として表現できる場合)、次の機械を使用して、固定点構造を維持しながらファンクターを変更できます。場所：

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)
于 2016-07-19T16:19:13.240 に答える