有什么像cata但你可以匹配内部结构？

Question

我有这种语言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, ")"]

但是当使用lambda时,Apply我需要括号

(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元组参数,我想它会慢一些.

Answer 1

正如@chi,@ DanielWagner和我在评论中所指出的那样,以结构递归的方式进行这种漂亮的打印与括号的方法是" showsPrec方法".

最大的想法是不要将语法树折叠成a 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"

通过替换Boola Int,可以将这种方法推广到具有任意优先级的括号运算符,如@ DanielWagner的链接答案所述.