Groups & Decisions

GROUP(d) means: try to render d on one line. If it fits within remaining width, render flat. Else: render with line breaks.

This is the critical decision in a pretty printer.

Algorithm:

Hughes' (predecessor) algorithm could be exponential. Wadler's improvement: linear.

Wadler's idea: pretty(width, ribbon, doc) returns a layout. Layout chooses for each GROUP.

Pseudocode:

Each GROUP makes one decision. Once decided, contained children inherit the parent's decision.

Bestcase O(n). Worstcase still O(n) for greedy variant. Optimal layout minimizes height + adheres to width.

Real prettier and Wadler descendents use this exact pattern.