Lambda演算AST漂亮打印：如何在Show实例中正确添加括号？

要正确处理λ项打印时的括号缺失问题，核心是利用Haskell的showsPrec和showParen函数，通过给不同语法结构分配优先级，精准控制括号的生成逻辑。

首先明确λ项的AST基础定义（假设你使用类似结构）：

data Term = Var String
          | Abs String Term
          | App Term Term
          deriving (Eq)

优先级规则设计 #

λ项的语法优先级遵循行业通用约定：

• 变量（Var）：优先级最高，永远不需要括号
• 应用（App）：左结合，优先级中等，高于抽象
• 抽象（Abs）：优先级最低，绑定范围尽可能向右延伸

给各构造子分配具体优先级数值：

• Var: 11（最高）
• App: 10
• Abs: 5（最低）

Show实例实现 #

基于上述优先级，编写showsPrec的具体实现：

instance Show Term where
  -- 变量直接输出，无需括号
  showsPrec _ (Var x) = showString x
  
  -- 抽象表达式：当前上下文优先级>5时自动包裹括号
  showsPrec p (Abs x t) = showParen (p > 5) $
    showString "\\" <> showString x <> showString ". " <> showsPrec 6 t
  
  -- 应用表达式：左结合，右子项用更高优先级触发括号
  showsPrec p (App t1 t2) = showParen (p > 10) $
    showsPrec 10 t1 <> showString " " <> showsPrec 11 t2

逻辑细节解释 #

1. 抽象（Abs）：

   • showParen (p > 5)：当抽象出现在优先级更高的上下文（比如应用的参数位置）时，自动添加括号，例如f (\x. x)
   • showsPrec 6 t：给抽象的body传递优先级6（高于Abs自身的5），嵌套抽象（比如\f. \x. f x）不会触发额外括号，符合语法习惯

2. 应用（App）：

   • showParen (p > 10)：仅当应用出现在更高优先级上下文时才加括号（这类场景极少）
   • 左子项用showsPrec 10：应用是左结合，f g h等价于(f g) h，左子项如果是应用，优先级相等不会触发括号，直接输出连续应用
   • 右子项用showsPrec 11：比应用优先级10高，右子项如果是应用（比如f (g h)）会自动包裹括号，避免歧义

验证你的案例 #

对于表达式Abs "f" (Abs "x" (App (Var "f") (App (Var "f") (Var "x"))))，打印结果为：

\f. \x. f (f x)

完全符合预期。

其他测试案例：

• App (Abs "x" (Var "x")) (Var "y") → (\x. x) y（正确包裹抽象）
• App (App (Var "f") (Var "g")) (Abs "x" (Var "x")) → f g (\x. x)（正确处理右子项的抽象）

内容的提问来源于stack exchange，提问作者A..