Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP3400

Assignment 1 Written

March 1, 2024

Note: The hard questions that comprise only 4/60 marks on this assessment are pro-visioned to test for topic mastery (the requirement for obtaining a seven). These questions are well beyond the level of difficulty of exam questions and therefore skip-ping them will not impair ones ability to write the final.

Lambda Calculus

You must use Haskell ordering in the following questions.

Question 1. Easy [4 marks]

Demonstrate that

(λn fx. f (nfx)) (λsz.s(s z))

reduces to the β-normal form

λfx. f(f(fx))

Question 2. Medium [4 marks]

Demonstrate that

(λxyz. z (z x))(λtf . t)(λp. p p p)(λq. q) a

reduces to the β-normal form

λf . a

Question 3. Hard [2 marks]

Reduce the following λ-calculus to its β-normal form or show it to be divergent.

(λxyz. xz (yz))((λxy. x)((λxyz. xz (yz))(λx. x)))(λxy. x) x y

Unnecessary α-conversions will be penalized.

Principal Types

Because we can automatically evaluate this section please submit PrincipalType.hs to the A1 Programming Assessment – this question still counts towards the written part. This also serves as a reminder that there are three more questions to do in addition to the ones on this sheet.

There is no partial credit for this section. You are not allowed to use undefined or type annotations.

Question 4. Easy [2 marks]

Define a function typeA such that

> :type typeA

typeA :: (a -> b, a) -> b

up to renaming of the type variables. Your function does not have to be total but should not be undefined.

Question 5. Easy [2 marks]

Same instructions as Question 4 but with

typeB :: ((a, a) -> [b]) -> a -> (a, [b])

Question 6. Medium [2 marks]

Same instructions as Question 4.

typeC :: (a -> b -> c -> d -> r) -> ((a, b) -> (c, d) -> r)

Question 7. Medium [2 marks]

Same instructions as Question 4 but with

typeD :: (c -> a -> b) -> (c -> a) -> (c -> b)

Question 8. Hard [2 marks]

Same instructions as Question 4 but with

typeE :: (a -> b) -> ((a -> c) -> d) -> ((b -> c) -> [d])

Induction

Question 9. Medium [10 marks]

Equilateral triangles can be tiled with smaller triangles in the following way:

and so on.

Note each triangle (asides T0) is comprised of four copies of the previous triangle.

Prove Tn can be covered with the following tile so that only the top triangle is left uncovered.

For example, for T1 and T2 can be covered in the following way

Note: This question will be marked very strictly. We will be looking for the presence of all necessary components of induction to be stated clearly. You will be marked down for being unnecessarily verbose. Every statement you write should be clearly inferred from the statements that precede it (not statements that come after).