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