haskell - Make [StackExp] instance of Expr class -

i make class expr arithmetic operations

class expr   mul :: -> ->    add :: -> ->   lit :: integer -> 

i want "parse" this: mul ( add (lit 3) (lit 2)) (lit 4) = (3+2)*4

and have data type:

data stackexp = pushi integer               | pushb bool               | add               | mul               | ,               | or                 deriving show 

and

type program = [stackexp] --i use type function of stack calculator later 

my task is: need make instance of expr type program

more concrete - want make transformation: mul ( add (lit 3) (lit 2)) (lit 4) ->>> [pushi 2, pushi 3, add, pushi 4, mul]

i have problems because receive [[stackexp]] @ output of instance declaration.

my try:

instance expr program   lit n = (pushi n):[]   add exp1 exp2 = exp1:(exp2:[add])    mul exp1 exp2 = exp1:(exp2:[mul]) 

i don't know how concatenate sub-expressions list

---------------- compiler error looks this------------------------

couldn't match type `[stackexp]' `stackexp'     expected type: stackexp       actual type: program 

..........

so, want want compile abstract syntax of expression language (the type class expr) code simple stack machine (a list of elements of type stackexpr).

one problem run that, in haskell 98 or haskell 2010, cannot declare [stackexpr] instance of class. example, ghc complain with

illegal instance declaration `expr [stackexp]'   (all instance types must of form (t a1 ... an)    a1 ... *distinct type variables*,    , each type variable appears @ once in instance head.    use -xflexibleinstances if want disable this.) in instance declaration `expr [stackexp]' 

to work way around this, define program type isomorphism (rather mere type synonym have now):

newtype program = p [stackexp] deriving show 

and make program instance of class expr. (alternatively, enable flexibleinstances suggested error message above.)

now can write required instance declaration:

instance expr program   mul (p x) (p y) = p (x ++ y ++ [mul])   add (p x) (p y) = p (x ++ y ++ [add])   lit n           = p [pushi n] 

that is, multiplication , addition, first compile operands , produce, respectively, mul or add instruction; literals produce corresponding push instruction.

with declaration, get, example:

> mul (add (lit 3) (lit 2)) (lit 4) :: program p [pushi 3,pushi 2,add,pushi 4,mul] 

(not quite in example. swap order of operands add. addition commutative, assume version acceptable well.)

---

of course more fun write small evaluator stack programs:

eval :: program -> [integer] eval (p es) = go es []       go [] s                   = s     go (pushi   n : es) s     = go es (n : s)     go (add : es) (m : n : s) = go es ((m + n) : s)     go (mul : es) (m : n : s) = go es ((m * n) : s) 

(note ignoring instructions deal booleans here seem deal integer expressions anyway.)

now have, example,

> eval (mul (add (lit 3) (lit 2)) (lit 4)) [20] 

which seems right.