How to tell whether parentheses are necessary or not?

Question

I have written a parser in Haskell, which parses formulas in the form of string inputs and produces a Haskell data type defined by the BNF below.

formula ::=  true  
         |  false  
         |  var  
         |  formula & formula  
         |  ∀ var . formula
         |  (formula)

    var ::=  letter { letter | digit }*

Now I would like to create an instance of Show so that I can nicely print the formulas defined by my types (I don't want to use deriving (Show)). My question is: How do I define my function so that it can tell when parentheses are necessary? I don't want too many, nor too little parentheses.

For example, given the formula ∀ X . (X & Y) & (∀ Y . Y) & false which, when parsed, produces the data structure

And (And (Forall "X" (And (Var "X") (Var "Y"))) (Forall "Y" (Var "Y"))) False

we have

   Too little parentheses:    ∀ X . X & Y & ∀ Y . Y & false
   Too much parentheses:      (∀ X . (((X) & (Y)))) & (∀ Y . (Y)) & (false)
   Just right:                ∀ X . (X & Y) & (∀ Y . Y) & false

Is there a way to gauge how many parenthesis are necessary so that the semantics is never ambiguous? I appreciate any feedback.

Bicolor

See showsPrec, which shows something with a given operator Precedence. – Mahayana

@AJFarmar Can you recommend any tutorials on how to use showsPrec? The documentation I'm finding on it is quite minimal. – Bicolor

@AJFarmar Or perhaps provide an answer :) – Bicolor

It's also a matter of taste. In my own preferred convention, ∀ X has the lowest precedence, so that ∀ X . A & B means ∀ X . (A & B), and not (∀ X . A) & B. (Sometimes the other precedence is used, instead.) Haskell also makes \ x -> to extend as to the right as possible. You have to choose the precedence. – Hatbox

@Hatbox Normally I would agree with you, but given what I'm using this grammar for, it turns out that giving lower precedence to conjunction is more convenient. My question is not about choosing the precedence, but rather about how to actually implement the show function so that parentheses are printed minimally. – Bicolor

There's plenty of information on showsPrec already available. A quick google search reveals this SO question, which I think is very helpful. – Mahayana

Note that, in order to implement showPrec, you have to choose a precedence for your symbols. Essentially, you do have to choose which one between ∀ X . (A & B) and (∀ X . A) & B can/should be written without parentheses. You want the latter, so the first will have parentheses -- that's OK. You need to assign a "precedence level" for your operators, and implement showPrec to add parentheses when you are in a context with a too high (I think) precedence. – Hatbox

I would suggest not using Show. Show is meant to output Haskell code, such that copy-pasting that code can (roughly) rebuild the original data. This should go into its own function. @chi's answer is still correct, and you can use all the ShowS stuff to implement your new function, but it should not be called show. – Premillenarian

Answer 1

Untested pseudocode:

instance Show Formula where
   showsPrec _p True  = "True"
   showsPrec _p False = "False"
   showsPrec p (And f1 f2) = showParen (p > 5) $
      showsPrec 5 f1 . (" & " ++) . showsPrec 5 f2
   showsPrec p (Forall x f) = showParen (p > 8) $
      ("forall " ++ x ++) . showsPrec 8 f
   ...

(I should probably use showString instead of those ++ above. It should work anyway, I think.)

Above, the integer p represents the precedence of the context where we are showing the current formula. For example, if we are showing f inside f & ... then p will have the precedence level of &.

If we need to print a symbol in a context which has higher precedence, we need to add parentheses. E.g. if f is a | b we can't write a | b & ..., otherwise it is interpreted as a | (b & ...). We need to put parentheses around a | b. This is done by the showParen (p > ...).

When we recurse, we pass the precedence level of the symbol at hand to the subterms.

Above, I chose the precedence levels randomly. You need to adjust them to your tastes. You should also check that the levels you choose play along the standard libraries. E.g. printing Just someFormula should not generate things like Just a & b, but add parentheses.

Hatbox

I think you're fine without showString :P. – Premillenarian

@Premillenarian It's only a matter of "style", indeed. :) – Hatbox

I understand that you chose them randomly, but could you clarify what the integers 5 and 8 are actually doing here? Why not 1 and 2? – Bicolor

@LukeCollins In principle, their value does not really matter, only their ordering does. However, one should try to choose the right ordering wrt the levels already used by the standard libraries. Otherwise, a formula will be printed correctly on its own, but incorrectly if e.g. inside a Just as the last example I wrote shows. In my experiments Just x gives level 11 to x, so to trigger parentheses. Instead [x] gives level 0 to x -- no parentheses needed here. Probably choosing your levels between 1 and 10 should be OK. – Hatbox