Homework 2

Instructions

The source code of this homework can be found here. You should fill in the definitions of the required functions but do not change the types of the functions.

How to submit: Send an email to niki.vazou@imdea.org with subject Haskell-Course'19:HW2 and attach this file.

> module HW2 where
> import Prelude hiding (sum, Either(..))
> import Data.Monoid
> import Control.Parallel.Strategies

Problem 1: Eithers are Functors, Applicatives & Monads

The data type Either a b contains

• either a Left value a,
• or a Right value b.

> data Either a b = Left a | Right b 
>   deriving (Show, Eq)

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

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

2. Give a proof that the two functor laws are satisfied by your definition.

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

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

4. Monads: Define a monad instance of Either, that satisfies the monad laws. So that, for example:

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

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

Problem 2: Monadic Lambda Evaluation

Given the data type of expressions

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

you are asked to define its monadic instance.

1. Functors: Define the Functor instance of Exp.

> 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. Functor Laws: Give a proof that the two functor laws are satisfied by your definition.

3. Applicatives: Define the Applicative instance of Exp.

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

4. Monads: Define the Monad instance of Exp.

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

5. Optional What does the (>>=) operator for this type do?

Problem 3: Map Reduce

1. Chunkables: The Chunkable type class has the method chunk i x that cuts its input x into lists of length as most i.

> class Chunkable a where 
>   chunk :: Int -> a -> [a]

Define lists as chunkable instances so that

ghci> chunk 2 [1]
[[1]]
ghci> chunk 2 [1..5]
[[1,2],[3,4],[5]]
ghci> chunk 6 [1..5]
[[1,2,3,4,5]]

Generally, each element if chunk i x has length no more than i, and the the chunks exactly reconstruct the list:

forall i, x. mconcat (chunk i x) == x

> instance Chunkable [a] where
>   chunk = error "Define me!"

2. Parallel Mapping: Using the parallel functions from the library Control.Parallel.Strategies, we define a parallel mapping function pmap f xs that applies f to each element in xs in parallel.

> pmap :: (a -> b) -> [a] -> [b]
> pmap = parMap rseq

Side-Note 1: If you actually check on the description of rseq, you will discover that pmap is not really really parallel. For the shake of simplicity, let’s assume it is.

Side-Note 2: Parallelization is only possible because the argument function is effect-free, as enforced by the type system. If f had effects, then the order that the effects would be executed, would be undetermined.

Use chunk, pmap and a monoid function to define the mapReduce i f x function below that

• chunks the input x in chunks of size at most i,
• maps f to each chunk, in parallel, and
• concatenates the result list.

> mapReduce :: (Chunkable a, Monoid b) 
>           => Int -> (a -> b) -> (a -> b) 
> mapReduce = error "Define me!"

Hint: This should be an one line definition!

Then for example, you can parallelize the sum function from the lecture:

> sum :: [Int] -> Sum Int 
> sum = mconcat . map Sum  

So that

ghci> sum [1..100]
Sum {getSum = 5050}
mapReduce 10 sum [1..100]
Sum {getSum = 5050}

In general:

forall xs, i. sum xs = mapReduce i sum xs

Which generalizes to every function f

forall f, i. f = mapReduce i f

3. Parallel Reducing: As we parallelized mapping, we can also parallelize the “reduce” stage of map reduce.

Use chunk and pmap from before to define a parallelized version of the monoid mconcat method, so that pmconcat i xs

• if xs has length less than i, then calls mconcat, otherwise
• chunks the input list xs,
• applied mconcat in parallel, and
• recurses on the concatenated chunks.

> pmconcat :: Monoid a => Int -> [a] -> a 
> pmconcat = error "Define me!"

Hint: pmconcat is recursively defined.

Use pmconcat to define a “two-level” parallel mapReduce, that parallelized both the “map” and “reduce” stages:

> mapReduce2 :: (Chunkable a, Monoid b) 
>           => Int -> (a -> b) -> (a -> b) 
> mapReduce2 = error "Define me!"

Hint: mapReduce2 can be defined with an one charactet edit from mapReduce.

So that

mapReduce2 == mapReduce