Functional Programming Exercise Session 7

1. Consider the following datatype of arithmetic expressions:

   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
   

2. Write a function that returns the number of operations in an expression

   size : Expr -> Nat
   

   For example, the size of exampleExpr is 2.

3. Write a function that evaluates an expression

   eval : Expr -> Int
   

   for example,

   > eval exampleExpr
   > 17 : Int
   

4. Modify your expression type to include varaibles as follows:

   Name : Type
   Name = String
   
   data Expr : Type where
     Num : Int -> Expr
       Add : Expr -> Expr -> Expr
       Mul : Expr -> Expr -> Expr
       Var : Name -> Expr
   

5. Modify the size and show functions to work with the new Expr type.

6. A Context is an assignment of Names to Ints , 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.

7. Modify your 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.

8. Modify your Expr datatype to include subtraction and division. Then, modify show, size, and eval to work with this new type.

9. (More Difficult / Optional) Write a parser for your type of expressions

     parseExpr : String -> Maybe Expr
   

   The representation of Exprs 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.