我有这种语言AST
data ExprF r = Const Int
| Var String
| Lambda String r
| EList [r]
| Apply r r
deriving ( Show, Eq, Ord, Functor, Foldable )
我想将其转换为字符串
toString = cata $ \case
Const x -> show x
Var x -> x
EList x -> unwords x
Lambda x y -> unwords [x, "=>", y]
Apply x y -> unwords [x, "(", y, ")"]
但是当在
Apply
中使用lambda时,我需要括号(x => x)(1)
但我无法将内部结构与cata相匹配
toString :: Fix ExprF -> String
toString = cata $ \case
Const x -> show x
Var x -> x
Lambda x y -> unwords [x, "=>", y]
Apply (Lambda{}) y -> unwords ["(", x, ")", "(", y, ")"]
Apply x y -> unwords [x, "(", y, ")"]
有没有比
para
更好的解决方案?toString2 :: Fix ExprF -> String
toString2 = para $ \case
Const x -> show x
Var x -> x
Lambda x (_,y) -> unwords [x, "=>", y]
EList x -> unwords (snd <$> x)
Apply ((Fix Lambda {}),x) (_,y) -> unwords ["(", x, ")", "(", y, ")"]
Apply (_,x) (_,y) -> unwords [x, "(", y, ")"]
看起来很丑。即使只在一个地方需要它,我也需要在任何地方删除fst元组参数,我想它会比较慢。
最佳答案
正如@ chi,@ DanielWagner和我在评论中指出的那样,以结构递归的方式进行带括号的漂亮打印的方法是“ showsPrec
方法”。
最重要的想法不是将语法树折叠成String
,而是折叠成函数Bool -> String
。这给我们带来了一定程度的上下文敏感度:我们将使用该额外的Bool
参数来跟踪我们当前是否处于应用程序左侧。
parens x = "(" ++ x ++ ")"
ppAlg :: ExprF (Bool -> String) -> (Bool -> String)
ppAlg (Const x) isBeingApplied = show x
ppAlg (Var x) isBeingApplied = x
ppAlg (Lambda name body) isBeingApplied = p ("\\" ++ name ++ " -> " ++ body False)
where p = if isBeingApplied then parens else id
ppAlg (EList es) isBeingApplied = unwords (sequenceA es False)
ppAlg (Apply fun arg) isBeingApplied = fun True ++ " " ++ arg False
根据当前在语法树中的位置,我们将
isBeingApplied
的值传递给递归调用。请注意,我们要传递的True
的唯一位置是fun
大小写正文中Apply
的参数。然后,在Lambda
情况下,我们检查该参数。如果当前项是应用程序的左手部分,则我们在lambda后面加上括号;如果不是,我们不会。在顶层,将整棵树折叠成一个函数
Bool -> String
,我们为它传递False
的参数-我们目前不在应用程序的上下文中-以获取String
。pp :: Expr -> String
pp ex = cata ppAlg ex False
ghci> pp $ app (lam "x" (var "x")) (cnst 2)
"(\\x -> x) 2"
通过用
Bool
替换Int
,该方法可以推广到具有任意优先级的括号运算符,如@DanielWagner's linked answer所述。