# TallCat Webpage of the Compositional Systems and Methods group at TalTech.

# 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 `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.

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 `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`.