Capstone B: the syntax tree

The syntax tree as a value

The tree of the previous lesson is an ordinary data type, and a data Expr = Num Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr instance Show Expr where show (Num n) = show n show (Add a b) = "(" ++ show a ++ " + " ++ show b ++ ")" show (Sub a b) = "(" ++ show a ++ " - " ++ show b ++ ")" show (Mul a b) = "(" ++ show a ++ " * " ++ show b ++ ")" show (Div a b) = "(" ++ show a ++ " / " ++ show b ++ ")"

Every operation is parenthesised, which is more brackets than a reader needs and exactly what a parser can read back without precedence questions.

The program

module Main (main) where data Expr = Num Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr instance Show Expr where show (Num n) = show n show (Add a b) = "(" ++ show a ++ " + " ++ show b ++ ")" show (Sub a b) = "(" ++ show a ++ " - " ++ show b ++ ")" show (Mul a b) = "(" ++ show a ++ " * " ++ show b ++ ")" show (Div a b) = "(" ++ show a ++ " / " ++ show b ++ ")" size :: Expr -> Int size (Num _) = 1 size (Add a b) = 1 + size a + size b size (Sub a b) = 1 + size a + size b size (Mul a b) = 1 + size a + size b size (Div a b) = 1 + size a + size b sample :: Expr sample = Add (Num 1) (Mul (Num 2) (Num 3)) main :: IO () main = do print sample print (size sample) print (Sub (Num 10) (Div (Num 8) (Num 2)))

ghc -Wall -O1 -o ast ast.hs
./ast

(1 + (2 * 3))
5
(10 - (8 / 2))

Why a Show of your own