Make [StackExp] instance of Expr class

Question

I make class Expr for arithmetic operations

class Expr a where
  mul :: a -> a -> a 
  add :: a -> a -> a
  lit :: Integer -> a

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

and i have data type:

data StackExp = PushI Integer
              | PushB Bool
              | Add
              | Mul
              | And
              | Or
                deriving Show

and

type Program = [StackExp] --i use this type for function of stack calculator later

my task is: i need to make instance of Expr for type Program

more concrete - i want to make this transformation: mul ( add (lit 3) (lit 2)) (lit 4) ->>> [PushI 2, PushI 3, Add, PushI 4, Mul]

i have problems because i receive [[StackExp]] at the output of my instance declaration.

my try:

instance Expr Program where
  lit n = (PushI n):[]
  add exp1 exp2 = exp1:(exp2:[Add]) 
  mul exp1 exp2 = exp1:(exp2:[Mul])

i don't know how to concatenate all sub-expressions into list

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

Couldn't match type `[StackExp]' with `StackExp'
    Expected type: StackExp
      Actual type: Program

..........

sorry, i think i solve problem just now: add exp1 exp2 = exp1 ++ exp2 ++ [Add] mul exp1 exp2 = exp1 ++ exp2 ++ [Mul] — Сергей Кузминский
If it works you can answer your own question so this one won't still look unsolved. — Daniel Gratzer

Stefan Holdermans Stefan Holdermans · Accepted Answer · 2013-05-04T20:23:35

So, what you basically want to do is you want to compile from the abstract syntax of your expression language (the type class Expr) to code for a simple stack machine (a list of elements of type StackExpr).

One problem that you immediately run into then is that, in just Haskell 98 or Haskell 2010, you cannot declare [StackExpr] an instance of a class. For example, GHC will complain with

Illegal instance declaration for `Expr [StackExp]'
  (All instance types must be of the form (T a1 ... an)
   where a1 ... an are *distinct type variables*,
   and each type variable appears at most once in the instance head.
   Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `Expr [StackExp]'

To work your way around this, you could define Program as a type isomorphism (rather than as a mere type synonym as you have now):

newtype Program = P [StackExp] deriving Show

and then make Program an instance of the class Expr. (Alternatively, you could enable FlexibleInstances as suggested by the error message above.)

Now we can write the required instance declaration:

instance Expr Program where
  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, for multiplication and addition, we first compile the operands and then produce, respectively, the Mul or Add instruction; for literals we produce the corresponding push instruction.

With this declaration, we get, for your example:

> mul (add (lit 3) (lit 2)) (lit 4) :: Program
P [PushI 3,PushI 2,Add,PushI 4,Mul]

(Not quite as in your example. You swap the order of the operands to Add. As addition is commutative, I will assume that this version is acceptable as well.)

Of course it is more fun to also write a small evaluator for stack programs:

eval :: Program -> [Integer]
eval (P es) = go es []
  where
    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 that I am ignoring instructions that deal with Booleans here as you only seem to deal with integer expressions anyway.)

Now we have, for your example,

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

which seems about right.

Make [StackExp] instance of Expr class

1 Answers