Kata: Mathematical AST - Display

Few weeks ago, we have tackled the Mathematical AST.

We only handled going from a reverse polish notation, post-fixed, to a final number, as follows:

eval :: String -> Int
eval = top . foldl (flip go) emptyMemory . words
  where
    go :: String -> Memory Int -> Memory Int
    go =
      \case
        "+" -> operator (+)
        "-" -> operator (-)
        "*" -> operator (*)
        n -> number (read n)

One of the remaining parts is to convert it back to a regular infix notation.

We are in the typical case where we could leverage an intermediate representation, a.k.a. a dedicated type.

The first step is to transpose the case above into constructors, as follows:

data Expr
  = Val Int
  | Add Expr Expr
  | Minus Expr Expr
  | Mul Expr Expr

The next step is to recursively evaluate the expression until we get an Int, as follows:

exprEval :: Expr -> Int
exprEval =
  \case
    Val x -> x
    Add x y -> exprEval x + exprEval y
    Minus x y -> exprEval x - exprEval y
    Mul x y -> exprEval x * exprEval y

To move forward, we should leverage them in the eval function, as follows:

eval :: String -> Int
eval = exprEval . top . foldl (flip go) emptyMemory . words
  where
    go :: String -> Memory Expr -> Memory Expr
    go =
      \case
        "+" -> operator Add
        "-" -> operator Minus
        "*" -> operator Mul
        n -> number $ Val $ read n

Note: we will skip the refactoring, which exposes Expr

Few years ago, I was binge-watching Ekmett's Twitch videos, and I discovered that Show instances were defined over showsPrec, defined as follows:

class Show a where
    showsPrec :: Int    -- ^ the operator precedence of the enclosing
                        -- context (a number from @0@ to @11@).
                        -- Function application has precedence @10@.
              -> a      -- ^ the value to be converted to a 'String'
              -> ShowS

-- | The @shows@ functions return a function that prepends the
-- output 'String' to an existing 'String'.  This allows constant-time
-- concatenation of results using function composition.
type ShowS = String -> String

It also comes with two helpers, declared as follows:

showString :: String -> ShowS
showParen :: Bool -> ShowS -> ShowS

We can then leverage them as follows:

-- exprShowInfix (eval "1 2 3 4 5 6 * * + * -") `shouldBe` "1 - 2 * (3 + 4 * 5 * 6)"
exprShowInfix :: Expr -> String
exprShowInfix = ($ "") . go 0
  where
    go :: Int -> Expr -> ShowS
    go p =
      \case
        Val x -> shows x
        Add x y -> showParen (p > 0) $ go 0 x . showString " + " . go 0 y
        Minus x y -> showParen (p > 0) $ go 0 x . showString " - " . go 0 y
        Mul x y -> go 1 x . showString " * " . go 1 y

Conversely, you can also derive prefix notation, as follows:

exprShowPrefix :: Expr -> String
exprShowPrefix = ($ "") . go
  where
    go :: Expr -> ShowS
    go =
      \case
        Val x -> shows x
        Add x y -> showString "+ " . go x . showString " " . go y
        Minus x y -> showString "- " . go x . showString " " . go y
        Mul x y -> showString "* " . go x . showString " " . go y