CODEWITHSUNDEEP
haskell
Markiy99
Markiy99

Reputation: 83

Haskell: Evaluate any Ast into a string

I have an assigment where I have to program an evaluation function eval::Ast -> String which evaluates any Ast into a string. for example:

>eval (parse "hel + lo") 
"hello"

> eval (parse "mi + 2 * la")
"milala"

I've made a parse-function that e.g. takes "hel + lo" and returns Plus (Word "hel") (Word "lo")

But I am very unsure of what the function (and types) should look like as there are multiple types involved in the evaluation of the AST... Anyone who can put me in the right direction?

The AST is defined as

data Ast 
 = Word String
 | Num Int
 | Mult Ast Ast
 | Plus Ast Ast
 | Minus Ast Ast
 deriving (Eq, Show)

Upvotes: 1

Views: 383

Answers (1)

chepner
chepner

Reputation: 531205

eval :: AST -> String is what defines the semantics of your operations. For example, eval (Plus (Word x) (Word y)) == x ++ y.

However, what should eval (Plus x y) produce if both arguments are numbers? Should it concatenate them, or add them numerically? What if either one itself is one of the Plus, Minus, or Mul values? You would need to evaluate them first, but then you can't tell if a result like "2" is really a string, or the result of a number.

You also need to decide if every AST can be evaluated: does Mul (Word "x") (Word "y") make sense? If not, what String would you return?

I would suggest two things:

First, define a simplify function that takes care of reducing the AST to something simpler. It will take care of doing things like numerical arithmetic in the case of Plus (Num ...) (Num ...), but leave things like Word x or Plus (Word x) (Num y) unchanged.

simplify :: AST -> AST
simplify (Num x) = Num x  -- Easy case done for you; no simplification necessary
simplify (Word x) = ...
-- Hint: in each of the following, you need to recursively simplify the operands.
-- Once you do that, you can either simplify further, or return a new
-- node to be evaluated.
simplify (Plus x y) = ...
simplify (Minus x y) = ...
simplify (Mul x y) = ...

Second, define eval :: AST -> Either String String, will first use simplify on its argument, then do case-by-case conversions of ASTs to Strings where feasible, and returning an appropriate error message where it isn't.

eval :: AST -> Either String String
eval x = eval' (simplify x)
   where eval' (Word x) = Right x  -- Easy case done for you
         eval' (Num x) = ...
         -- simplify will have reduced all the Num + Num, Num - Num, and
         -- Num * Num nodes to single Num nodes already.
         eval' (Plus (Word x) (Word y)) = x ++ y  -- Other easy case done above
         eval' (Plus x y) = ...
         eval' (Minus (Word x) (Word y)) = ...
         eval' (Minus x y) = ...
         eval' (Mul (Word x) (Word y)) = ...
         eval' (Mul x y) = ...

Note that you could conceivably define some combinations in either eval' or simplify, e.g.

simplify (Plus (Word x) (Word y)) == Word $ x ++ y

leaving the more complicated (and possibly impossible) cases to eval.

Upvotes: 2

Related Questions