代写COMP3400 Assignment 2 Written 2024代做迭代

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.