Het volgende algebraïsch data type beschrijft de abstracte syntax voor simpele aritmetische expressies.

data Exp = Const Int
         | Add Exp Exp 
         | Sub Exp Exp 
         | Mul Exp Exp
         deriving Show

In de informatica worden berekeningen echter vaak voorgesteld door een (voor de computer eenvoudigere) lijst van stack-operaties. Een programma dat deze uitvoert noemen we een stack machine.

data Inst = IPush Int
          | IAdd
          | ISub
          | IMul
          deriving Show

type Prog  = [Inst]
type Stack = [Int]

1. Schrijf een interpreter eval :: Exp -> Int die aritmetische expressies evalueert.
2. Schrijf een interpreter run :: Stack -> Prog -> Stack die het gegeven programma uitvoert op de gegeven stack. Een instructie met 2 operandi zal de bovenste waarde op de stack als rechterlid nemen, en die daaronder als linkerlid.
3. Schrijf een functie compile :: Exp -> Prog die voor gegeven expressie een programma schrijft, dat na uitvoering eindigt met het resultaat van de expressie bovenaan de stack.