Wie mit AST mit Cofree Annotation arbeiten?

Question

Ich habe diese einfache Expr AST und ich kann es leicht zu String konvertieren.

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] 

Jetzt möchte ich eine zusätzliche Daten hinzufügen. So versuche ich Cofree

type LineNumber = Int 
type Expr2 = Cofree ExprF LineNumber 

I Expr-Expr2

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

Aber ich kann nicht herausfinden, umwandeln kann zu verwenden, wie Expr2-String

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

auch zu konvertieren, ist Cofree der beste Weg, um dieses Annotationsproblem zu lösen?

Answer 1

Eine alternative Möglichkeit zur Kommentierung Ihres Syntaxbaums besteht darin, die Anmerkung in den Basisfunktor zu schreiben.

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

Wir werden das Funktors Produkt verwenden, um eine Anmerkung (innerhalb eines K) zu jeder Schicht des Baumes zu befestigen.

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

Wenn Sie können Anmerkungen erzeugen, während nur eine einzige Schicht des Baumes Inspektion (das heißt, Annotations-Erzeugungs Code kann als eine natürliche Transformation ausgedrückt werden), dann können Sie das folgende Bit von Maschinen verwenden die modifizieren Funktors während die Fixpoint Struktur an Ort und Stelle zu halten:

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

Dies ist von begrenztem Nutzen, wenn es, wie die meisten interessanten Anmerkungen wie Typ-Prüfung benötigen Traversal des Syntaxbaums.

Sie können den Code verwenden, um eine Expr abzureißen, indem Sie einfach die Anmerkungen ignorieren. Gegeben eine Algebra für 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] 

... können Sie es abzureißen entweder ein Expr oder AnnExpr:

compileE :: Expr -> Prog 
compileE = cata compile_ 

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