Webpage of the Compositional Systems and Methods group at TalTech.
data Expr : Type where
Num : Int -> Expr
Add : Expr -> Expr -> Expr
Mul : Expr -> Expr -> Expr
with associated Show
instance:
Show Expr where
show (Num x) = show x
show (Add x y) = "(" ++ show x ++ " + " ++ show y ++ ")"
show (Mul x y) = "(" ++ show x ++ " * " ++ show y ++ ")"
For example,
exampleExpr : Expr
exampleExpr = Add (Num 2) (Mul (Num 3) (Num 5)
and
> show exampleExpr
> "(2 + (3 * 5))" : String
size : Expr -> Nat
For example, the size of exampleExpr
is 2
.
eval : Expr -> Int
for example,
> eval exampleExpr
> 17 : Int
Name : Type
Name = String
data Expr : Type where
Num : Int -> Expr
Add : Expr -> Expr -> Expr
Mul : Expr -> Expr -> Expr
Var : Name -> Expr
Modify the size and show functions to work with the new Expr
type.
Context
is an assignment of Name
s to Int
s , represented as follows:
Context : Type
Context = List (Name,Int)
The idea being that if (x,k)
is present in the context, the name x
stands for the integer k
. If x
is stands for multiple elements in a Context
, we consider only the one closest to the beginning of the Context
. Write a function
find : Name -> Context -> Maybe Int
that returns what the input name stands for in the input context, if anything.
eval
function to evaulate our new variable arithmetic expressions in a context:
eval : Context -> Expr -> Maybe Int
The idea is that if we encounter a variable that is not assigned a value by the context, we ought to fail and return Nothing
.
Modify your Expr
datatype to include subtraction and division. Then, modify show
, size
, and eval
to work with this new type.
parseExpr : String -> Maybe Expr
The representation of Expr
s as strings is up to you. If you do this exercise, consider also changing your implementation of show
so that (parseExpr . show) x
is Just x
.