COMP3400
2024
Assignment 2 Written
May 3, 2024
In addition to this written work there are three coding questions.
Either
The Functor and Applicative for the Either data-type is as follows:
1 instance Functor (Either a) where
2 fmap f (Right x) = Right (f x)
3 fmap f (Left x) = Left x
4
5 instance Applicative (Either e) where
6 pure = Right
7 Left e <*> _ = Left e
8 Right f <*> r = fmap f r
When writing your proofs use the line numbers given above when justifying your steps.
Question 1. Easy [4 marks]
Show Either satisfies the second functor law:
9 fmap (g . h) = fmap g . fmap h
Question 2. Medium [6 marks]
Show Either satisfies the third applicative law:
10 x <*> pure y = pure (\g -> g y) <*> x
ZipWith
Recall the alternate definition for a list applicative given in Tutorial 9.
1 instance Functor [] where
2 fmap _ [] = []
3 fmap g (x:xs) = g x : (fmap g xs)
4
5 instance Applicative [] where
6 pure f = repeat f
7 [] <*> _ = []
8 _ <*> [] = []
9 (f:fs) <*> (x:xs) = (f x) : (fs <*> xs)
When writing your proofs use the line numbers given above when justifying your steps.
Question 3. Medium [10 marks]
Use structural induction to show this Applicative satisfies the forth applicative law:
10 x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z
Parsing
Question 4. Medium [10 marks]
Complete the grammar for polynomials given below.
1 Polynom ::= ? | ? "+" ?
2
3 Factors ::= Factor | Factor Factors
4
5 Factor ::= "(" ? ")" | ?
6
7 Mono ::= ? | ? | ? | ? | Constant
8
9 Constant ::= ?
Hint: The order of precedence (lowest to highest) for polynomial operations is: Ad-dition, Multiplication, Brackets.