CODEWITHSUNDEEP
haskellfunctional-programming
hamid
hamid

Reputation: 2079

How to evaluate an expression built out of an ADT

Here's my ADT:

data Ex a = I Integer  --integer
           | Add (Ex a) (Ex a) --add 
           | Variable a --variable
           | Def [(a, Ex a)] (Ex a) --defining local variables

And here's my evaluate function:

eval :: Ex a -> Integer
eval (I n) = n
eval (Add e1 e2) = eval e1 + eval e2

How do I continue eval for Variable and Def?

Upvotes: 0

Views: 239

Answers (2)

Satvik
Satvik

Reputation: 11218

Some more hints to help you write the solution yourself.

Some suggestions

  • You need to perform lookup on the list of type [(a,Ex a)] and hence need Eq a constraint on that.
  • Your evaluation can fail if you have not defined a local variable and used it. In that case the eval function should return Nothing otherwise Just answer.
  • I have written most part of your code the only place you need to write is for Variable a case. Which is very simple as you just need to lookup a in xs and return the value after evaluating it if lookup succeeds else Nothing.

The code becomes 

eval :: Eq a => Ex a -> Maybe Integer
eval = eval' []
  where eval' :: Eq a => [(a, Ex a)] -> Ex a -> Maybe Integer
        eval' _ (I n) = Just n
        eval' xs (Add e1 e2) = liftA2 (+) (eval' xs e1) (eval' xs e2) -- liftA2 from Control.Applicative
        eval' xs (Variable a) = -- write your code here
        eval' xs (Def ys e) = eval' (ys ++ xs) e -- Think of the order in which you want to combine two binding if same named variable is present in both xs and ys.

Upvotes: 1

dave4420
dave4420

Reputation: 47072

Here's a hint:

eval :: Ex a -> Integer
eval = eval' []
  where eval' :: [(a, Integer)] -> Ex a -> Integer
        eval' _ (I n) = n
        -- etc

Upvotes: 1

Related Questions