A Pretty But Not Greedy Printer (Functional Pearl)

Jean-Philippe Bernardy, University of Gothenburg, gives the second presentation in the second panel, Functional Programming Techniques, in the ICFP 2017 conference. This paper proposes a new specification of pretty printing which is stronger than the state of the art: we require the output to be the shortest possible, and we also offer the ability to align sub-documents at will. We argue that our specification precludes a greedy implementation. Yet, we provide an implementation which behaves linearly in the size of the output. The derivation of the implementation demonstrates functional programming methodology.