{-----------------------------------------
  Expression interpreter: trivial version
  (no parsing, simple printing, no tracing)
 -----------------------------------------}

--------------------
-- Expression trees and their fold

data Expr = Lit Int | Opr Op Expr Expr  deriving (Eq, Show)

fold f g (Lit n)     = f n
fold f g (Opr o l r) = g o (fold f g l) (fold f g r)


--------------------
-- Operators, evaluation and pretty-printing

data Op = Add | Mul | Sub  deriving (Eq, Show)

syn Add = "+" ;  syn Mul = "*" ;  syn Sub = "-"
sem Add = (+) ;  sem Mul = (*) ;  sem Sub = (-)

idtr = fold Lit  Opr
eval = fold id   sem
prti = fold show inf

inf o l r = concat [ "(", l, " ", syn o, " " ,r ,")" ]


--------------------
-- Some test data

[(+:), (*:), (-:)] = map Opr [Add, Mul, Sub]

t0 = (Lit 2 +: Lit 3) *: ((Lit 5 +: Lit 6) -: Lit 4)
t1 = (Lit 2 *: Lit 3) +:  (Lit 4 *: Lit 5)


------------------------------------------------------------