Fast pretty-printing library

A pretty printer turns a tree structure into indented text, such that the indentation reflects the tree structure. To minimise the number of lines, substructures are put on a single line as far as possible within the given line-width limit.

An pretty-printed example with 35 characters line-width:

if True
   then if True then True else True
   else
      if False 
         then False 
         else False

To obtain the above the user of a library only has to convert their tree structure into a document of type Doc.

data Exp = ETrue | EFalse | If Exp Exp Exp

toDoc :: Exp -> Doc
toDoc ETrue = text "True"
toDoc EFalse = text "False"
toDoc (If e1 e2 e3) =
  group (nest 3 (
    group (nest 3 (text "if" <> line <> toDoc e1)) <> line <>
    group (nest 3 (text "then" <> line <> toDoc e2)) <> line <>
    group (nest 3 (text "else" <> line <> toDoc e3))))

A document represents a set of layouts. The function pretty then takes a desired maximal printing width and a document and selects the layout that fits best.

Another example filling lines with elements of a list:

list2Doc :: Show a => [a] -> Doc
list2Doc xs = text "[" <> go xs <> text "]"
  where
  go [] = empty
  go [x] = text (show x)
  go (x:y:ys) = text (show x) </> text ", " <> go (y:ys)

main = putStrLn (pretty 40 (list2Doc [1..20]))

The output is

[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10
, 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18
, 19 , 20]

FPretty is an implementation of the simple combinators designed by Phil Wadler. The library uses a single associative combinator <> to concatenate documents with empty as identity. There is a primitive document for potential line breaks, i.e., its two layouts are both a line break and a space. The group combinator then enforces that all potential line breaks within a document must be layouted in the same way, i.e. either line breaks or spaces.

The time complexity is linear in the output size. In contrast, all other pretty printing libraries (original Phil Wadler, PPrint by Leijen, Hughes / Peyton Jones) use more or less backtracking, and their speed depends unpredictably on the desired output width.

Also FPretty provides both relative and absolute indentation via nest and align, whereas HughesPJ provides only relative indentation.

FPretty uses far less space than other pretty printing libraries for large documents. It does require space linear in the nesting depth of nest/align combinators; however, having these deeply nested leads to a bad layout anyway.

Unlike other libraries, FPretty does not provide several rendering modes, but could be extended to do so.

The combinators are a subset of those of PPrint and are similar to HughesPJ to make moving from one library to the other as painless as possible.

For more implementation notes see http://www.cs.kent.ac.uk/~oc/pretty.html or Doitse Swierstra and Olaf Chitil: Linear, bounded, functional pretty-printing. Journal of Functional Programming, 19(1):1-16, January 2009.