Haskell 中具有运算符优先级和关联性的漂亮打印语法树

Question

是否有任何常用的方法或什至是一个库来漂亮地打印（和解析）带有（二元）运算符的语法树，这些运算符分配了关联性和优先级，以便结果使用尽可能少的括号？

以命题演算的公式为例：

data Formula
    = Atom String
    | Not (Formula)
    | And (Formula) (Formula)
    | Or (Formula) (Formula)
    | Imp (Formula) (Formula)

假设优先级是 Imp < Or < And < Not（因此 Not 绑定最多）并且 And, Or 和 Imp 应该关联到右边；所以例如 Imp (And (Imp (Atom "A") (Atom "B")) (Atom "A")) (Atom "B") 应该打印类似 (A -> B) /\ A -> B.

的内容

当然这可以通过模式匹配来实现，但是这很乏味而且很不愉快；我正在从 Coq 证明助手中寻找与此符号类似的简单内容：

Notation "A /\ B" := (and A B) (at level 80, right associativity).

它生成一个解析器和一个漂亮的打印机。

Answer 1

Formula 的 Show 实例可能如下所示：

instance Show Formula where
  showsPrec _ (Atom name) = showString name
  showsPrec p (Not formula) = showParen (p > 3) $
    showString "\+ " . showsPrec 3 formula
  showsPrec p (And lhs rhs) = showParen (p > 2) $
    showsPrec 3 lhs . showString " /\ " . showsPrec 2 rhs
  showsPrec p (Or lhs rhs) = showParen (p > 1) $
    showsPrec 2 lhs . showString " \/ " . showsPrec 1 rhs
  showsPrec p (Imp lhs rhs) = showParen (p > 0) $
    showsPrec 1 lhs . showString " -> " . showsPrec 0 rhs

这将允许任何 Formula 成为具有适当括号的 shown：

main = print $ Imp (And (Imp (Atom "A") (Atom "B")) (Atom "A")) (Atom "B")

打印（print 是 putStrLn . show）：

(A -> B) /\ A -> B

Haskell 中具有运算符优先级和关联性的漂亮打印语法树

Pretty Printing Syntax Tree with Operator Precedence and Associativity in Haskell

haskell

abstract-syntax-tree

pretty-print