我有这种语言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所述。

09-17 15:04
查看更多