This assign­ment is due April 12 at 11:59 PM. Pull the Github repos­i­tory and start work­ing on Assign­ment3.hs. This home­work is based on that of Niki Vazou.

Either as a Functor, Applicative, and Monad

Recall the Either data type, which is either a Left with value a or a Right with value b.

data Either a b = Left a | Right b
deriv­ing (Show, Eq)

1. Define a func­tor instance of Either that sat­is­fies the func­tor laws. So that, for exam­ple:

Pre­lude> fmap (+42) (Left 0)
Left 0
Pre­lude> fmap (+42) (Right 0)
Right 42

2. Define an applica­tive instance of Either that sat­is­fies the applica­tive laws. So that, for exam­ple:

Pre­lude> pure 0 :: Either Int Int
Right 0
Pre­lude> pure (+42) <*> (Left 0)
Left 0
Pre­lude> pure (+42) <*> (Right 0)
Right 42

3. Define a monad instance of Either that sat­is­fies the monad laws. So that, for exam­ple:

Pre­lude> pairs (Right  0) (Right 1)
Right (0,1)
Pre­lude> pairs (Right  0) (Left  1)
Left 1
Pre­lude> pairs (Left   0) (Right 1)
Left 0
Pre­lude> pairs (Left   0) (Left 1)
Left 0

where pairs is given by

pairs xs ys = do
x <- xs
y <- ys
return (x,y)

Let us sup­pose we have a sim­ple lan­guage of expres­sions

data Exp a = EVar a | EVal Int | EAdd (Exp a) (Exp a)

1. Define a func­tor instance for Expr.

instance Func­tor Exp where
-- fmap :: (a -> b) -> Exp a -> Exp b
fmap f (EVar x)   = unde­fined "Define me!"
fmap f (EVal n)   = unde­fined "Define me!"
fmap f (EAdd x y) = unde­fined "Define me!"

2. Define an applica­tive instance for Expr.

instance Applica­tive Exp where
-- pure :: a -> Exp a
pure x = unde­fined "Define me!"

-- (<*>) :: Exp (a -> b) -> Exp a -> Exp b
ef <*> e = unde­fined "Define me!"

3. Define a monad instance for Expr.