Expression evaluation tree in Haskell

expression-evaluation expression-trees 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?

Accepted Answer

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.

:)



Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why