Expression evaluation tree in Haskell

Question

In an exam today I was asked to create an expression evaluation tree in Haskell. Usually the answer is as simple as:

data Expr = Value Integer
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr

And to evaluate it, you just use a function such as:

eval :: Expr -> Integer
eval (Value x) = x
eval (Add l r) = eval l + eval r
eval (Sub l r) = eval l - eval r
eval (Mul l r) = eval l * eval r

However today, we were given a data type:

data Op = Add
        | Sub
        | Mul

So I assumed to create the expression tree I could just do:

data Expr = Value Integer
          | Op Expr Expr

And use the same eval function. However, I have since written that function and loaded it into GHCI, but it does not seem to work. Could anyone explain why this doesn't work?

Answer 1

You must define a data constructor (providing a name)

data Expr = Value Integer | Compute Op Expr Expr
                            ^^^^^^^

then

eval :: Expr -> Integer
eval (Value x) = x
eval (Compute Add l r) = eval l  + eval r

and so on.

:)