haskellpretty-print# Pretty print application (Lambda-calculus)

I want to pretty print an AST of lambda-terms. Therefore, I am creating show instances in order to achieve this, but I am having one problem. Whenever I print applications, I obviously lose the parenthesis closing each expression.

For example `Abs f (Abs x (App f (App f x)))`

. I wish the result to be `\\f. \\x. f (f x)`

instead of `\\f. \\x. f f x`

.
How can I achieve define this in instance show? I understand there are functions showsPrec or showParen but I'm having a bit of trouble using this because I don't know how I should define the precedence.

Solution

showsPrec and operator precedences has a good summary:

`infix n`

: use`showParen (p > n)`

,`showsPrec (n+1)`

on the left, and`showsPrec (n+1)`

on the right`infixl n`

: use`showParen (p > n)`

,`showsPrec n`

on the left, and`showsPrec (n+1)`

on the right`infixr n`

: use`showParen (p > n)`

,`showsPrec (n+1)`

on the left, and`showsPrec n`

on the right- non-infix: use
`showParen (p > 10)`

and`showsPrec 11`

on the arguments

The reason is that the precedence parameter of `showsPrec`

represents the precedence of the surrounding expression, so you need to include parentheses when that expression is an operator that binds more tightly than the the expression you’re showing. The `+ 1`

is to treat the precedence as if it were a bit higher, so that expressions of the *same* precedence will get parentheses when overriding the associativity of an operator.

By convention, `showsPrec`

implementations typically use the same precedence numbers as ordinary Haskell code, where `0`

is lowest (as in `f $ x`

) and `10`

is highest (as in `f x`

). You can check the precedence of an operator with `:info`

in GHCi.

```
λ :info +
type Num :: * -> Constraint
class Num a where
(+) :: a -> a -> a
...
-- Defined in ‘GHC.Num’
infixl 6 +
λ :info *
type Num :: * -> Constraint
class Num a where
...
(*) :: a -> a -> a
...
-- Defined in ‘GHC.Num’
infixl 7 *
```

So, for example, because `+`

is `infixl 6`

and `*`

is `infixl 7`

, if an addition like `1 + 2`

is an operand of a multiplication like `_ * 3`

, then there must be parentheses around the addition like `(1 + 2) * 3`

, because `1 + 2 * 3`

would mean something different.

Similarly, since `+`

is `infixl`

, the expression `5 + 6`

*should* get parentheses when it’s the child of `4 + _`

, giving `4 + (5 + 6)`

, but *shouldn’t* when it appears as the child of `_ + 7`

, because `5 + 6 + 7`

= `(5 + 6) + 7`

.

Given this type:

```
data Exp x
= Abs x (Exp x)
| App (Exp x) (Exp x)
| Var x
```

A `Show`

instance could look like this.

```
instance (Show x) => Show (Exp x) where
showsPrec prec exp0 = case exp0 of
Abs var exp ->
showParen
(prec > appPrec)
(showString "\\" .
shows var .
showString ". " .
shows exp)
App exp1 exp2 ->
showParen
(prec > appPrec)
(showsPrec appPrec exp1 .
showString " " .
showsPrec (appPrec + 1) exp2)
Var var ->
shows var
where
appPrec = 10
```

We can test that like so.

```
λ newtype Name = Name Char
λ instance Show Name where show (Name c) = [c]
λ let { f = Name 'f'; x = Name 'x' } in print (Abs f (Abs x (App (Var f) (App (Var f) (Var x)))))
\f. \x. f (f x)
```

Now, with all that said, `Show`

isn’t really the right abstraction for this. (If you’re familiar with Python, Haskell’s `show`

is supposed to serve the same function as Python’s `__repr__`

, not `__str__`

.) `Show`

is supposed to be a debugging tool that shows you exactly how a value is constructed, not pretty-print it in a way that could hide information. I can promise you won’t regret writing `deriving stock (Show)`

and using a different abstraction for pretty-printing.

However, what abstraction *should* you use? A popular choice is the prettyprinter package, which includes a `class Pretty`

.

```
class Pretty a where
pretty :: a -> Doc ann
default pretty :: Show a => a -> Doc ann
pretty = viaShow
```

But this doesn’t have a built-in way of handling precedence, and we can’t add an argument to the class method, `pretty`

. In cases like this, my preferred approach is to add a wrapper type.

```
data WithPrec a = WithPrec Int a
```

Then we can create an instance for the wrapper type, and just call that from the proper instance.

```
instance (Pretty x) => Pretty (Exp x) where
pretty = pretty . WithPrec 0
instance (Pretty x) => Pretty (WithPrec (Exp x)) where
pretty (WithPrec prec exp0) = case exp0 of
Abs var exp ->
prettyParen
(prec > appPrec)
("\\" <>
pretty var <>
"." <+>
pretty exp)
App exp1 exp2 ->
prettyParen
(prec > appPrec)
(pretty (WithPrec appPrec exp1) <+>
pretty (WithPrec (appPrec + 1) exp2))
Var var ->
pretty var
where
appPrec = 10
prettyParen :: Bool -> Doc a -> Doc a
prettyParen True x = parens x
prettyParen False x = x
```

Besides precedence information like `WithPrec`

, you can keep other kinds of context in wrapper types. For operators you can include associativity to save parentheses in some circumstances. In general, it could be any “style” information you want to use during formatting, and this kind of contextuality can be abstracted with the `Env`

comonad if you like.

Now you can have both pretty-printing and a derived `Show`

.

```
λ print (Abs "f" (Abs "x" (App (Var "f") (App (Var "f") (Var "x")))))
Abs "f" (Abs "x" (App (Var "f") (App (Var "f") (Var "x"))))
λ print (pretty (Abs "f" (Abs "x" (App (Var "f") (App (Var "f") (Var "x"))))))
\f. \x. f (f x)
```

- How can I refactor from error to an ExceptT?
- How can I generate a random sequence of elements from a list in Haskell?
- Problem with quantified types and pattern matching
- Why is the `unicode-show` package necessary?
- Get sum of int or integer in Haskell
- Java 8: streams and the Sieve of Eratosthenes
- Can iterate be written with a fold?
- Haskell function with data pattern match and second argument gives Equations have different numbers of arguments
- How to use (->) instances of Monad and confusion about (->)
- Trouble understanding Haskell type unification with a nested `fmap`
- why ghc does not support PIE and Full RelRO in linux?
- Controlling Wai logger messages
- How do Haskell compilers decide whether to allocate on the heap or the stack?
- How can date/time format of Yesod logger be configured?
- In Haskell's Turtle library, how to copy a file, but preserve the file date
- Could not deduce (Semigroup (TimedEvents a))
- Instance of class with Data family yielding error "Couldn't match expected type"
- Is there a way to get a Haskell setup on Windows without an installation? (Copy + paste)
- Haskell parse error on input `<-'
- Inline assembly in Haskell
- How do I deal with arbitrary length tuple to build up a complex SQL query for Haskell's postgresql-simple's query function?
- Extract liftIO and runSql in separate function (Haskell)
- How to query NodeJS stream 'meta data'?
- Building multiple executables in the default Haskell Stack project
- Take elements of a list up to and including the first value that satisfies some predicate in Haskell
- How are Hackage package names mapped to 'cabal install' names?
- Insert entity into DB with manually created foreign key in Persistent library (Haskell)
- couldn´t match type 'IO´ with ´[]` inside a do
- Why doesn't contravariance apply in certain cases like [b] → Int < a → Int
- How does the Haskell compiler handle the 'where' statement?