showsPrec和运算符优先级

Question

我之前问过这个问题,但似乎我的问题太过狭隘.那么让我们看看我是否可以解释我实际上在追求什么.

假设我有一些类型支持几个二元运算符,每个运算符具有不同的优先级和关联性.如何编写Show正确包含子表达式的实例？

我知道我在这里很密集,但每次尝试这样做都会出错.必须有一些机械程序,你可以遵循正确的工作,但我找不到它.有人可以告诉我一个例子吗？

我知道这最终归结为包装所有东西showParen,并使用showsPrec正确的幻数显示子表达式,我可以使它几乎工作,但它在所有情况下都无法正常工作.

---

编辑:请考虑以下代码

data Expr =
  Const Int |
  Expr :+: Expr |
  Expr :-: Expr |
  Expr :*: Expr |
  Expr :/: Expr

infixl 6 :+:
infixl 6 :-:
infixl 7 :*:
infixl 7 :/:

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showParen (p > 6) $ (showsPrec 6 x) . (" :+: " ++) . (showsPrec 6 y)
     x :-: y -> showParen (p > 6) $ (showsPrec 6 x) . (" :-: " ++) . (showsPrec 6 y)
     x :*: y -> showParen (p > 7) $ (showsPrec 7 x) . (" :*: " ++) . (showsPrec 7 y)
     x :/: y -> showParen (p > 7) $ (showsPrec 7 x) . (" :/: " ++) . (showsPrec 7 y)

这几乎正常:

*Main> Const 1 :+: Const 2 :*: Const 3 :+: Const 4
1 :+: 2 :*: 3 :+: 4
*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(1 :+: 2) :*: (3 :+: 4)

但不完全:

*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
1 :+: 2 :-: 3 :-: 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
1 :+: 2 :-: 3 :-: 4

因此看起来优先级是正常的,但关联性是不可靠的.

Answer 1

既然showsPrec没有任何方法可以获得上下文的关联性,我认为没有办法解决这个问题,完全得到最小的Haskell括号.为确保正确性而不增加必要的冗余parens,请>=在以下showParen条件下使用:

  showsPrec p e0 =
    case e0 of
     Const n -> shows n
     x :+: y -> showParen (p >= 6) $ (showsPrec 6 x) . (" :+: " ++) . (showsPrec 6 y)
     x :-: y -> showParen (p >= 6) $ (showsPrec 6 x) . (" :-: " ++) . (showsPrec 6 y)
     x :*: y -> showParen (p >= 7) $ (showsPrec 7 x) . (" :*: " ++) . (showsPrec 7 y)
     x :/: y -> showParen (p >= 7) $ (showsPrec 7 x) . (" :/: " ++) . (showsPrec 7 y)

然后产生

*Main> Const 1:+:Const 2:*:Const 3:+:Const 4
(1:+:2:*:3):+:4
*Main>(Const 1:+:Const 2):*: (Const 3:+:Const 4)
(1:+:2):*:(3:+:4)
*Main> Const 1:+:Const 2: - :Const 3: - :Const 4
((1: +:2): - :3): - :4
*Main> Const 1:+:Const 2: - :( Const 3: - :Const 4)
(1:+:2): - :(3: - : 4)

哪个看起来不是那么好,但不是太糟糕,当然不会像showParen (p > n)版本一样错.基本上,这给出了最小的括号,如果我们只有infix,没有infixl或infixr.

如果您只想要那些真正需要的parens,那么您需要传播更多信息而不仅仅是Int上下文固定.我在HaTeX的符号数学扩展思想中实现了那种东西; 本质上它只是infixl在运行时镜像Haskell 等注释.例如,

     exaDisp $ 5 - (4 - 3) + 2 + 1

然后呈现像

Answer 2

以下Show实例将Expr使用最小括号打印类型:

data Expr =
  Const Int |
  Expr :+: Expr |
  Expr :-: Expr |
  Expr :*: Expr |
  Expr :/: Expr

infixl 6 :+:
infixl 6 :-:
infixl 7 :*:
infixl 7 :/:

instance Show Expr where
  showsPrec p e0 =
    case e0 of
     Const n -> showParen (p > 10) $ showString "Const " . showsPrec 11 n
     x :+: y -> showParen (p > 6) $ showsPrec 6 x . showString " :+: " . showsPrec 7 y
     x :-: y -> showParen (p > 6) $ showsPrec 6 x . showString " :-: " . showsPrec 7 y
     x :*: y -> showParen (p > 7) $ showsPrec 7 x . showString " :*: " . showsPrec 8 y
     x :/: y -> showParen (p > 7) $ showsPrec 7 x . showString " :/: " . showsPrec 8 y

这导致:

*Main> Const 1 :+: Const 2 :*: Const 3 :+: Const 4
Const 1 :+: Const 2 :*: Const 3 :+: Const 4
*Main> (Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
(Const 1 :+: Const 2) :*: (Const 3 :+: Const 4)
*Main> Const 1 :+: Const 2 :-: Const 3 :-: Const 4
Const 1 :+: Const 2 :-: Const 3 :-: Const 4
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)
Const 1 :+: Const 2 :-: (Const 3 :-: Const 4)

一般规则是

• infix n:使用showParen (p > n),showsPrec (n+1)在左侧和showsPrec (n+1)右侧
• infixl n:使用showParen (p > n),showsPrec n在左侧和showsPrec (n+1)右侧
• infixr n:使用showParen (p > n),showsPrec (n+1)在左侧和showsPrec n右侧
• 非中缀:使用showParen (p > 10)和showsPrec 11论证

按照这一原则,将总是产生正确的语法以最小的括号,除了在一个角落里的情况:它可以产生模糊的输出,如果你有infixl和infixr具有相同优先级级别的构造.只要你不这样做,你应该没事.

我怎么知道使用什么参数showParen？这是为了匹配Haskell为派生Show实例所做的事情.我们可以测试这样的:

data T = P :# P | T P
  deriving Show

infix 6 :#

data P = P

instance Show P where
  showsPrec p P = shows p

我们可以看到,infix 6 :#的Show T实例调用showsPrec 7的参数:#,并且也只有在优先级> 6显示了括号:

*Main> showsPrec 6 (P :# P) ""
"7 :# 7"
*Main> showsPrec 7 (P :# P) ""
"(7 :# 7)"

对于普通构造函数T,生成的实例调用showsPrec 11参数并显示优先级> 10的parens:

*Main> showsPrec 10 (T P) ""
"T 11"
*Main> showsPrec 11 (T P) ""
"(T 11)"