# Monad Enlightenment

This assignment is due April 12 at 11:59 PM. Pull the Github repository and start working on `Assignment3.hs`

. This homework 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 deriving (Show, Eq)

1. Define a functor instance of `Either`

that satisfies the functor laws. So that, for example:

Prelude> fmap (+42) (Left 0) Left 0 Prelude> fmap (+42) (Right 0) Right 42

2. Define an applicative instance of `Either`

that satisfies the applicative laws. So that, for example:

Prelude> pure 0 :: Either Int Int Right 0 Prelude> pure (+42) <*> (Left 0) Left 0 Prelude> pure (+42) <*> (Right 0) Right 42

3. Define a monad instance of `Either`

that satisfies the monad laws. So that, for example:

Prelude> pairs (Right 0) (Right 1) Right (0,1) Prelude> pairs (Right 0) (Left 1) Left 1 Prelude> pairs (Left 0) (Right 1) Left 0 Prelude> pairs (Left 0) (Left 1) Left 0

where `pairs`

is given by

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

## Monadic Lambda Evaluation

Let us suppose we have a simple language of expressions

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

1. Define a functor instance for `Expr`

.

instance Functor Exp where -- fmap :: (a -> b) -> Exp a -> Exp b fmap f (EVar x) = undefined "Define me!" fmap f (EVal n) = undefined "Define me!" fmap f (EAdd x y) = undefined "Define me!"

2. Define an applicative instance for `Expr`

.

instance Applicative Exp where -- pure :: a -> Exp a pure x = undefined "Define me!" -- (<*>) :: Exp (a -> b) -> Exp a -> Exp b ef <*> e = undefined "Define me!"

3. Define a monad instance for `Expr`

.

instance Monad Exp where -- return :: a -> Expr a return x = undefined "Define me!" -- (>>=) :: Exp a -> (a -> Exp b) -> Exp b (EVar x) >>= f = undefined "Define me!" (EVal n) >>= f = undefined "Define me!" (EAdd x y) >>= f = undefined "Define me!"

## Final Project

1. Submit a working version of your project. This is not your final version, but should be mostly complete. In particular, there should be some part of the code that is runnable and gives evidence that you are close to done. Please include a `README`

that indicates how to run it. We will be testing it out!

2. Describe what you have left to do in the `Assignment3.hs`

file.