Improving the display of Boolean formulas

Question

I want to implement a method to display a sentence formula in SML. The solutions I have found so far were of this type:

fun show (Atom a) = a
  | show (Neg p) = "(~ " ^ show p ^ ")"
  | show (Conj(p,q)) = "(" ^ show p ^ " & " ^ show q ^ ")"
  | show (Disj(p,q)) = "(" ^ show p ^ " | " ^ show q ^ ")";

This creates unnecessary curly braces:

((~p) & (q | r))

when that i would like to have:

~ p & (q | r)

I saw that Haskell has a function (display?) That does it nicely. Maybe someone helped me a little. How should I do it?

Answer 1

If you want to exclude extra parentheses, you will need to pass some priority information. For example, in Haskell, a function showsPrecimplements this pattern; he has type

showsPrec :: Show a => Int -> a -> String -> String

Int . String - , . , , , , Haskell ( ) .

, , , , , - . unbracketed . : ? , , , . "" - dCntxt - , , - dHere . bracket , .

data Formula
    = Atom String
    | Neg  Formula
    | Conj Formula Formula
    | Disj Formula Formula

precedence :: Formula -> Int
precedence Atom{} = 4
precedence Neg {} = 3
precedence Conj{} = 2
precedence Disj{} = 1

displayPrec :: Int -> Formula -> String
displayPrec dCntxt f = bracket unbracketed where
    dHere       = precedence f
    recurse     = displayPrec dHere
    unbracketed = case f of
        Atom s   -> s
        Neg  p   -> "~ " ++ recurse p
        Conj p q -> recurse p ++ " & " ++ recurse q
        Disj p q -> recurse p ++ " | " ++ recurse q
    bracket
        | dCntxt > dHere = \s -> "(" ++ s ++ ")"
        | otherwise      = id

display :: Formula -> String
display = displayPrec 0

.

*Main> display (Neg (Conj (Disj (Conj (Atom "a") (Atom "b")) (Atom "c")) (Conj (Atom "d") (Atom "e"))))
"~ ((a & b | c) & d & e)"