- More work on expression trees, and variable environments
- Applicative functors
- Assignment 7: trees, stacks, translation

```
data Arith
= Num Double
| Var String
| UnaryOp UnaryOp Arith
| BinOp BinOp Arith Arith
deriving (Eq, Show)
```

We need a way to track/specify the values of variables.

```
example1 =
BinOp Add
(BinOp Sub
(BinOp Mul
(BinOp Add (Num 3) (Num 4))
(Var "x"))
(UnaryOp Sqrt (Var "y")))
(BinOp Pow (Num 3) (Var "y"))
```

```
evaluate :: Environment -> Arith -> Double
evaluate _ (Num x) = x
evaluate env (Var s) =
case lookup s env of
Nothing -> error ("Unknown variable: " ++ s)
Just x -> x
evaluate env (UnaryOp Sqrt t) = sqrt (evaluate env t)
evaluate env (UnaryOp Neg t) = -(evaluate env t)
evaluate env (BinOp Add t1 t2) =
evaluate env t1 + evaluate env t2
evaluate env (BinOp Mul t1 t2) =
evaluate env t1 * evaluate env t2
evaluate env (BinOp Sub t1 t2) =
evaluate env t1 - evaluate env t2
evaluate env (BinOp Div t1 t2) =
evaluate env t1 / evaluate env t2
evaluate env (BinOp Pow t1 t2) =
evaluate env t1 ** evaluate env t2
```

Review: a functor `f`

is a type with one operation

```
fmap :: (a -> b) -> f a -> f b
fmap :: (a -> b) -> [a] -> [b]
fmap :: (a -> b) -> Maybe a -> Maybe b
fmap :: (a -> b) -> Either c a -> Either c b
```

You can use `(<$>)`

as a symbolic infix operator for fmap.

Applicative is an extension of functor that needs two additional functions:

```
(<*>) :: f (a -> b) -> f a -> f b
fmap :: (a -> b) -> f a -> f b
```

`(<*>)`

is sometimes pronounced “splat”.