# Notes week of 22 Oct

• More work on expression trees, and variable environments
• Applicative functors
• Assignment 7: trees, stacks, translation
main :: IO ()
main = return ()
data BinOp = Add | Sub | Mul | Div | Pow
deriving (Eq, Show)
data UnaryOp = Sqrt | Neg
deriving (Eq, Show)
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.

type Environment = [(String, Double)]
sampleEnv :: Environment
sampleEnv = [("x", 75), ("y", 17), ("x", 18), ("z", 72)]
example1 =
(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

# Applicative functors

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: pure :: a -> f a pure :: a -> [a] pure :: a -> Maybe a pure :: a -> Either c a  (<*>) :: f (a -> b) -> f a -> f b fmap :: (a -> b) -> f a -> f b (<*>) is sometimes pronounced “splat”. sqrt <$> Just 25
--> Just 5

sqrt :: Double -> Double

(+) :: Double -> Double -> Double

(+) <$> Just 5 sqrt <$> Just 5

(+) <\$> Just 8 <*> Just 7