modulePGF.Tree(Tree(..),tree2expr,expr2tree,prTree)whereimportPGF.CIdimportPGF.Exprhiding(Tree) --import Data.CharimportData.ListasList--import Control.Monad --import qualified Text.PrettyPrint as PP --import qualified Text.ParserCombinators.ReadP as RP -- | The tree is an evaluated expression in the abstract syntax -- of the grammar. The type is especially restricted to not -- allow unapplied lambda abstractions. The tree is used directly -- from the linearizer and is produced directly from the parser.dataTree=Abs[(BindType,CId)]Tree-- ^ lambda abstraction. The list of variables is non-empty|VarCId-- ^ variable|FunCId[Tree] -- ^ function application|LitLiteral-- ^ literal|Meta{-# UNPACK #-}!MetaId-- ^ meta variablederiving(Eq,Ord) ----------------------------------------------------- -- Conversion Expr <-> Tree ----------------------------------------------------- -- | Converts a tree to expression. The conversion -- is always total, every tree is a valid expression.tree2expr::Tree->Exprtree2expr=tree2expr[]wheretree2exprys(Funxts)=foldlEApp(EFunx) (List.map(tree2exprys)ts)tree2exprys(Litl)=ELitltree2exprys(Metan)=EMetantree2exprys(Absxst)=foldr(\(b,x)e->EAbsbxe) (tree2expr(List.mapsnd(reversexs)++ys)t)xstree2exprys(Varx)=caseList.lookupx(zipys[0..])ofJusti->EVariNothing->error"unknown variable" -- | Converts an expression to tree. The conversion is only partial. -- Variables and meta variables of function type and beta redexes are not allowed.expr2tree::Expr->Treeexpr2treee=abs[] []ewhereabsysxs(EAbsbxe)=absys((b,x):xs)eabsysxs(ETypede_)=absysxseabsysxse=casexsof[]->appys[]exs->Abs(reversexs) (app(mapsndxs++ys) []e)appxsas(EAppe1e2)=appxs((absxs[]e2):as)e1appxsas(ELitl)|List.nullas=Litl|otherwise=error"literal of function type encountered"appxsas(EMetan)|List.nullas=Metan|otherwise=error"meta variables of function type are not allowed in trees"appxsas(EAbs_xe)=error"beta redexes are not allowed in trees"appxsas(EVari)=iflengthxs>ithenVar(xs!!i)elseMetai---- AR 14/12/2010: work-around needed in PGF.Paraphrase.fromDefappxsas(EFunf)=Funfasappxsas(ETypede_)=appxsaseprTree::Tree->StringprTree=showExpr[].tree2expr