Wadler's Doc Type

Phil Wadler (2003): "A Prettier Printer". Define an algebraic data type:

Doc = NIL                          (empty)
    | TEXT(string)                 (literal text)
    | LINE                         (line break or space if grouped)
    | CONCAT(Doc, Doc)             (sequence)
    | NEST(int, Doc)               (indent contents by N)
    | GROUP(Doc)                   (try one-line; if no fit, multi-line)

Constructors + combinators:

Example: format a list:

When the list is short enough: [1, 2, 3]. When too long:

[
  1,
  2,
  3,
]

The same Doc renders both ways. The renderer decides based on width.

Why not directly produce strings? Because the decision "fit or break" depends on what comes AFTER the current point. The Doc representation defers this decision.

Other Doc types:

• align: indent to current column (for vertical alignment).
• flatten: force one-line variant.
• softbreak: break or empty.
• hardbreak: always break.

Wadler's algebra has nice properties: concat is associative; group(group(x)) == group(x). Reasoning is easy.

Real implementations: prettyprinter (Haskell), prettier (JS), Doc.PageMode.PageMode (Java), Wadler-pp (Python).