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
  deriv­ing (Show, Eq)

1. Define a functor instance of Either that satisfies the functor laws. So that, for example:

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

2. Define an applicative instance of Either that satisfies the applicative laws. So that, for example:

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 satisfies the monad laws. So that, for example:

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)

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

instance Monad Exp where
  -- return :: a -> Expr a
  return x = unde­fined "Define me!"

  -- (>>=) :: Exp a -> (a -> Exp b) -> Exp b
  (EVar x)   >>= f = unde­fined "Define me!"
  (EVal n)   >>= f = unde­fined "Define me!"
  (EAdd x y) >>= f = unde­fined "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.