showsPrec and operator precedences

Question

I asked about this before, but it seems I phrased the question too narrowly. So let's see if I can explain what I'm actually after.

Suppose I have some type that supports several binary operators, each with varying precedence and associativity. How do I write a Show instance that correctly brackets sub-expressions?

I know I'm being dense here, but I get this wrong every single time I try to do it. There must be some mechanical procedure you can follow to make this work out correctly, but I cannot find it. Can somebody walk me through an example?

I know this ultimately boils down to wrapping everything in showParen, and showing sub-expressions using showsPrec with the right magic number, and I can make it almost work, but it never quite works right in all circumstances.

---

Edit: Consider the following code

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)

This almost works correctly:

*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)

But not quite:

*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

So it looks like the precedence is OK, but the associativity is borked.

Jeconiah

Google suggests these two questions: Pretty Printing AST with Minimal Parentheses and Associativity and Precedence of Expressions when Generating C / C++ Code?. These may give you some ideas. I'm not sure whether this qualifies as a duplicate of one of those or not, but for now I lean towards "not a dup", since this question is in part about how to make the general techniques fit into the Haskell ecosystem smoothly. – Diverting

Answer 1

Since showsPrec hasn't any way to obtain the associativity of the context, I don't think it's possible to fix this as in, get exactly the minimal Haskell parenthesation back. To ensure correctness without adding more redundant parens than necessary, use >= in the showParen condition:

  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)

This then yields

*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)

Which doesn't look quite as nice as it could, but not too bad and certainly not wrong like the showParen (p > n) version. Basically, this gives what would be the minimal parenthesization if we had only infix, no infixl or infixr.

If you want only those parens to appear which are really necessary, you'll need to propagate more information than just an Int for context fixity. I implemented that kind of thing in my symbolic-math extension idea for HaTeX; essentially it just mirrors Haskell's infixl etc. annotations at runtime. For example,

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

is then rendered like

Closestool

Answer 2

The following Show instance will print the Expr type with minimal parentheses:

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

This results in:

*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)

The general rule is

• infix n: use showParen (p > n), showsPrec (n+1) on the left, and showsPrec (n+1) on the right
• infixl n: use showParen (p > n), showsPrec n on the left, and showsPrec (n+1) on the right
• infixr n: use showParen (p > n), showsPrec (n+1) on the left, and showsPrec n on the right
• non-infix: use showParen (p > 10) and showsPrec 11 on the arguments

Following this rule will always yield correct syntax with minimal parentheses, except in one corner case: It can produce ambiguous output if you have infixl and infixr constructors with the same precedence level. As long as you don't do that, you should be fine.

---

How did I know what arguments to use with showParen? It's to match what Haskell does for derived Show instances. We can test those like this:

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

infix 6 :#

data P = P

instance Show P where
  showsPrec p P = shows p

We can see that with infix 6 :#, the Show T instance calls showsPrec 7 on the arguments to :#, and also it shows parentheses only at precedences > 6:

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

And for the ordinary constructor T, the generated instance calls showsPrec 11 on the argument and shows parens at precedences > 10:

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

Cnidus

Answer 3

How about this:

prec :: Expr -> Int
prec (Const _) = 10
prec (_ :*: _) = 7
prec (_ :/: _) = 7
prec (_ :+: _) = 6
prec (_ :-: _) = 6

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

resulting in

*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 :-: Const 5)
1 + 2 - (3 - 4 - 5)
*Main> Const 1 :+: Const 2 :-: (Const 3 :-: (Const 4 :-: Const 5))
1 + 2 - (3 - (4 - 5))
*Main> Const 1 :+: Const 2 :-: (Const 3 :*: (Const 4 :/: Const 5))
1 + 2 - 3 * (4 / 5)
*Main> (Const 1 :*: (Const 2 :-: (Const 3 :*: (Const 4 :/: Const 5))))
1 * (2 - 3 * (4 / 5))

Andorra