A Pretty Printer Library in Haskell

宋方睿

i#maskray,me

What is a Pretty Printer

Use positioning, spacing, color, size, etc.

To make the content easier to view

Ruby Example

require 'pp'
PP.pp 10.times.to_a, $>, 29
PP.pp 10.times.to_a, $>, 30
p 10.times.to_a.size

indent

indent <<e
int foo(int k){if(k<1||k>2){printf("out of range\n")
printf("this function requires a value of 1 or 2\n");}else{
printf("Switching\n");switch(k){case 1:printf("1\n");break;case
2:printf("2\n");break;}}}
e

par

Topic

text "<html>" <> nest 2 (text "<body>" <> line <> text "</body>") <> "</html>"

Haskell

Function application (juxtaposition)

min 19 58
min(19, 58)
succ 0 + min 555 350
succ(0) + min(555, 350)

List

[Int]

Singly-linked list

std::slist<int>
[2,0,1,3] ++ [0,2]
[2,0,1,3] + [0,2]

Result:

[2,0,1,3,0,2]

String is List

type String = [Char]
['r','a','y']

Result:

"ray"

List Manipulation

take 5 [1,9,1,1,0,4,2,6]
[1,9,1,1,0,4,2,6][:5]

Result:

[1,9,1,1,0]
drop 5 [1,9,1,1,0,4,2,6]
[1,9,1,1,0,4,2,6][5:]

Result:

[4,2,6]
takeWhile odd [1,9,1,1,0,4,2,6]
from itertools import takewhile
odd = lambda x: bool(x % 2)
takewhile(odd, [1,9,1,1,0,4,2,6])

Result:

[1,9,1,1]

Type Signature

add :: Int -> Float -> Double
double add(int, float);

Function

suc :: Int -> Int
suc 0 = 1
suc 1 = 2
int suc(int x) {
  if (x == 0) return 1;
  if (x == 1) return 2;
  abort();
}
add :: Int -> Int -> Int
add 2 0 = 2
add 1 3 = 4
int add(int x, int y) {
  if (x == 2 && y == 0) return 2;
  if (x == 1 && y == 3) return 4;
  abort();
}

Algebraic data type / tagged union / variant

enum T { Y, L, L0, S, W, Q };
data T = Y | L | L0 | S | W | Q

Tagged Union

data J = X Float | Q Char Char
X 2.5
Q 'z' 'y'
struct J {int tag; union {float M; struct{char C0, C1;} Q;};};
struct J P; P.tag = 0; P.M = 2.5f;
struct J R; P.tag = 1; R.Q.C0 = 'z'; R.Q.C1 = 'y';

Rose Tree

struct RoseTree {
  int key;
  RoseTree *sub_trees;
};
data RoseTree = RoseTree Int [RoseTree]

Operators

Law of text & layout

text (s ++ t) == text s <> text t
text "" == nil
layout nil == ""
layout line == "\n"
layout (text x) == x
layout (x <> y) == layout x ++ layout y

nest

Lorem
ipsum
dolor
sit
amet
, consecteur

nest (Cont.)

Lorem
ipsum
dolor
sit
amet
, consecteur

nest (Cont.)

nest i nil == nil
nest 0 x == x
nest (i+j) x == nest i (nest j x)
nest i (text x) == text x
nest i (x <> y) == nest i x <> nest i y
 
layout (nest i line) == '\n' : replicate i ' '

A Simple ADT

data Doc = Nil
         | Text String Doc
         | Line Int Doc
Text "Lorem" (Line 1 (Text "ipsum (Line 3 …)))
text "Lorem" <> line <> indent <> text "ipsum" <> line <> indent <> indent <> indent <> …

Semantics

nil = Nil
text x = Text x Nil
line = Line 0 Nil

Nil <> x = x
(Text x y) <> z = Text x (y <> z)
(Line i x) <> y = Line i (x <> y)

nest i Nil = Nil
nest i (Text x y) = Text x (nest i y)
nest i (Line j x) = Line (i+j) (nest i x)

Semantics (Cont.)

layout Nil = ""
layout (Text x y) = x ++ layout y
layout (Line x y) = '\n' : replicate i ' ' ++ layout y

Example

data Tree = Node String [Tree]
tree (Node s ts) = text s <> (bracket ts)

bracket [] = nil
bracket ts = text "[" <> nest 2 (line <> trees ts) <> line <> text "]"

trees [t] = tree t
trees (t:ts) = tree t <> text "," <> line <> trees ts

Alternative Layouts

flatten :: Doc -> Doc

(<|>) :: Doc -> Doc -> Doc

Law of <|>

(x <|> y) <> z == (x <> z) <|> (y <> z)
x <> (y <|> z) == (x <> y) <|> (x <> z)
nest i (x <|> y) == (nest i x) <|> (nest i y)

Reduced to a normal form:

x0 <|> x1 <|> … <|> xn-1

Exponential Growth

(x0 <|> x1) <> (x2 <|> x3) <> (x4 <|> x5) <> …

ADT with union

data Doc = Nil
         | Text String Doc
         | Line Int Doc
         | Union Doc Doc
x <|> y = Union x y

Invariants

For Union x y, we require that:

Law of flatten

flatten nil == nil
flatten line == text " "
flatten (test x) == x
flatten (x <> y) = flatten x <> flatten y
flatten (nest i x) == flatten x
flatten (x <|> y) == flatten x

Best Layout

Prettier Line

best :: Doc -> Doc

best :: Int -> Int -> Doc -> Doc

best w k Nil = Nil
best w k (Line i x) = Line i (best w i x)
best w k (Text x y) = Text x (best w (k + length x) y)
best w k (Union x y) = if fits (w-k) xx yy
  where
    xx = best w k x
    yy = best w k y

fit :: Int -> Doc -> Bool

fit w x | w < 0 = False
fit w Nil = True
fit w (Text x y) = fit (w - length x) y
fit w (Line i x) = True

pretty :: Int -> Doc -> String

w x = layout (best w 0 x)

O(n2) → O(n)

To be continued …

Thanks

References