How to print expressions with binary operators using as few parentheses as possible. In this post, we avoid parentheses that are rendered unnecessary by precedence rules.
Consider the following type.
type op = Plus | Times type expr = Op of op * expr list | I of int
And here is a value:
let v = Op (Plus, [I 3; Op (Times, [I 5; I 7; Op (Plus, [I 4; I 2])]); I 2])
If we don't care about how many parentheses are printed, we'd write
open Format let op2s = function Plus -> '+' | Times -> '*' let rec pp_list sep pp ppf = function |  -> () | [x] -> fprintf ppf "%a" pp x | x::xs -> fprintf ppf "%a%c%a" pp x sep (pp_list sep pp) xs let rec pp ppf = function | Op (o, es) -> fprintf ppf "@[(%a)@]@," (pp_list (op2s o) pp) es | I x -> fprintf ppf "%d@," x let _ = pp std_formatter v
The rule for precedence is simple: It's safe to strip parentheses in
$(A \circ B) \bullet C$ if and only if $\circ$ has higher precedence than
$\bullet$. It would be nice to isolate the code that decides whether
parentheses are needed. We begin by removing grouping concerns from
let pp r ppf = function | Op (o, es) -> pp_list (op2s o) r ppf es | I x -> fprintf ppf "%d" x
We can recover parentheses everywhere with a simple Y-like combinator.
let rec y1 f ppf x = fprintf ppf "@[(%a)@]@," (f (y1 f)) x let pp1 = y1 pp let _ = pp1 std_formatter v
pp1 does (almost) the
same as the initial
the big difference being that we isolated the code that handles grouping.
Because of this, implementing a policy based on operator precedences is
simply a matter of defining another combinator.
let precedence = function | Op (Plus, _::_::_) -> 1 | Op (Times, _::_::_) -> 2 | _ -> 0 let rec y2 up f ppf x = let down = precedence x in let lp, rp = if down <= up && up <> 0 && down <> 0 then ("(", ")") else ("","") in fprintf ppf "@[%s%a%s@]@," lp (f (y2 down f)) x rp let pp2 = y2 0 pp let _ = pp2 std_formatter v