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

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