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)