blog

One can define a Num instance in Haskell for ASTs of expressions, viz.

data BinOp = Plus | Minus | Mul | Div
data Exp = Int Integer
         | BinOp BinOp Exp Exp
instance Num Exp where
    (+) = BinOp Plus
    (*) = BinOp Times
    (-) = BinOp Minus
fromInteger = Int

I use this in my Apple compiler.

sum over a list will construct a syntax tree:

λ:> sum [1,2,3,4,5::Exp]
(+ (+ (+ (+ (+ (int 0) (int 1)) (int 2)) (int 3)) (int 4)) (int 5))

This is a nice way to see the difference between foldl and foldr:

λ:> (foldl1 (+) [1,2,3,4,5::Exp])
(+ (+ (+ (+ (int 1) (int 2)) (int 3)) (int 4)) (int 5))
λ:> (foldr1 (+) [1,2,3,4,5::Exp])
(+ (int 1) (+ (int 2) (+ (int 3) (+ (int 4) (int 5)))))

Using the compiler backend, sum [1,2,3,4,5] can be used to define a series of assembly instructions that evaluates the sum of [1,2,3,4,5]:

λ:> pAsm $ evalAarch64 (sum [1,2,3,4,5])
    mov T5, #0x0
    add T4, T5, #0x1
    add T3, T4, #0x2
    add T2, T3, #0x3
    add T1, T2, #0x4
    add X0, T1, #0x5

Cute!