All of your answers will be auto-graded, so for coding problems you will be marked according to how many of our tests you pass. Incorrect answers that pass tests will be penalised accordingly. The auto-grader will only mark code that you upload to the exam by dragging it into the appropriate box from a file window.
Reading period: 10 minutes
Writing period: 60 minutes
Permitted materials: One A4 page with notes on both sides, Unannotated paper-based dictionary.
Questions are not of equal value.
All questions must be completed on this web form.
Your work is automatically saved and recorded as you type.
This is a closed examination. You may not copy this exam.
Question 1
[20 Marks]
Multichoice Questions (1100 and 1130)
These questions are for both COMP1100 and COMP1130 students. Each question is intended to have only one correct answer. Each question is worth 2.5 marks. An incorrect or missing answer is worth 0 marks, without further mark penalty.
1 i)
[2.5 Marks]
Sets and Functions
Let 𝔻
be the set {North,South,East,West}
and 𝔹
be the Booleans {True,False}
.
Which of the following defines a valid mathematical function f
with domain 𝔻
and codomain 𝔹
?
f(North)=True, f(South)=False | |
f(North)=True, f(South)=False, f(True)=East, f(False)=West | |
f(North)=True, f(South)=True | |
f(North)=True, f(South)=True, f(East)=True, f(West)=True | |
f(North)=True, f(South)=True, f(North)=False, f(East)=False, f(West)=False | |
1 ii)
[2.5 Marks]
Sets and Functions
Given any sets A
, B
, and C
, and projright
the right projection of A × B
, which of the following statements about the composition g . projright
is true?
It is a valid mathematical function for any function g :: A → C | |
It is a valid mathematical function for any function g :: A × B → C | |
It is a valid mathematical function for any function g :: B → C | |
It is a valid mathematical function for any function g :: C → A | |
It is a valid mathematical function for any function g :: C → A × B | |
It is a valid mathematical function for any function g :: C → B | |
1 iii)
[2.5 Marks]
Programming
If a whole program, written in .hs files, has been converted into instructions that a machine can run directly, we say it has been
Assembled | |
Compiled | |
Evaluated | |
Interpreted | |
Mechanised | |
1 iv)
[2.5 Marks]
Basic Types
Which statement about Int
and Integer
is true?
Elements of Int are bounded in size, whereas elements of Integer are not bounded | |
Elements of Integer are bounded in size, whereas elements of Int are not bounded | |
Int is a valid Haskell type, whereas Integer is not a valid Haskell type | |
Integer is a valid Haskell type, whereas Int is not a valid Haskell type | |
Int and Integer are two different names for the same type | |
1 v)
[2.5 Marks]
Basic Types
Consider the function
baz :: Bool -> Bool -> Bool
baz b c = (not b && c) || (b == c)
Which of the following is a complete English language description of all cases for which baz b c
will evaluate to True
?
b and c have the same values | |
b and c have different values | |
b is False or c is True | |
b is False and c is True | |
1 vi)
[2.5 Marks]
Algebraic Datatypes
Consider the datatype definition
data Qux = Rax Bool Bool Bool | Tix Bool | Vox Bool Bool
How many different values are elements of this datatype?
12 | |
14 | |
32 | |
48 | |
64 | |
1 vii)
[2.5 Marks]
Recursion with Lists
Consider the function
dividing :: [Double] -> Double
dividing list = dHelper 1.0 list
where
dHelper :: Double -> [Double] -> Double
dHelper x list = case list of
[] -> x
y:ys -> dHelper (y / x) ys
When applied to the list [2.5,5.5]
, what mathematical calculation is computed?
(2.5 / 1.0) / 5.5 | |
(2.5 / 5.5) / 1.0 | |
(5.5 / 2.5) / 1.0 | |
(5.5 / 1.0) / 2.5 | |
2.5 / (5.5 / 1.0) | |
5.5 / (2.5 / 1.0) | |
1 viii)
[2.5 Marks]
Parametric Polymorphism
Suppose we have the parametric polymorphic datatype definition
data Foo a b = Bar a b
Which of the following is a valid element of an instantiation of this type?
Bar 3 "hello" | |
Bar Int String | |
Foo 3 "hello" | |
Foo Int String | |
Question 2
[10 Marks]
Multichoice Questions (1130 ONLY)
These questions should be attempted only by COMP1130 students. Responses by COMP1100 students will be ignored. Instructions are otherwise as for the previous questions.
2 i)
[2.5 Marks]
Lambda Calculus
What are the free variables of the following lambda-calculus term?
λx.((λy. y z) y)(x z)
The empty set | |
{x} | |
{y} | |
{z} | |
{x,y} | |
{x,z} | |
{y,z} | |
{x,y,z} | |
2 ii)
[2.5 Marks]
Lambda Calculus
Consider the term
(λx. x (λy. x y) (λx. z x)) (y y)
Which one of the following lambda-calculus terms is (alpha-equivalent to) the result of one step of beta-reduction to this term?
(λx. x x (λx. z x)) (y y) | |
(λx. x (x (λx. z x))) (y y) | |
λx. y y (λy. x y) (λx. z x) | |
(λy. x y) (λx. z x) (y y) | |
y y (λw. y y w) (λx. z x) | |
y y (λw. y y w) (λx. z (y y)) | |
y y (λy. y y y) (λx. z x) | |
y y (λy. y y y) (λx. z (y y)) | |
2 iii)
[2.5 Marks]
Lambda Calculus
Assuming we have encodings of Booleans, consider the Barendregt encoding of natural numbers:0
as λx. x
n+1
as λx. if x then False else n
Now consider the lambda term
λx. if (x True) then False else (x False True)
On which inputs of (Barendregt encodings of) natural numbers will this evaluate to True
?
0 only | |
every number except 0 | |
1 only | |
every number except 1 | |
0 and 1 only | |
every number except 0 and 1 | |
every number | |
no numbers | |
2 iv)
[2.5 Marks]
Lambda Calculus
What is the complete beta-reduction of
(λw. w ((λx. x) w))(λy. y z)
according to strict evaluation?
→ (λw. w w)(λy.y z) → (λw. w w) z → z z | |
→ (λw. w w)(λy.y z) → (λy.y z)(λy.y z) → (λy.y z) z → z z | |
→ (λw. w ((λx. x) w)) z → (λw. w w) z → z z | |
→ (λw. w ((λx. x) w)) z → z ((λx. x) z) → z z | |
→ (λy.y z)((λx. x)(λy.y z)) → (λx. x)(λy.y z) z → (λx. x) z z → z z | |
→ (λy.y z)((λx. x)(λy.y z)) → (λx. x)(λy.y z) z → (λy.y z) z → z z | |
→ (λy.y z)((λx. x)(λy.y z)) → (λy.y z)(λy.y z) → (λy.y z) z → z z | |
Question 3
[30 Marks]
Programming Questions (1100 and 1130)
There are six Haskell files that you need to complete and submit. Each file contains exactly one function to complete, although you may define helper functions if you wish. You may use any Haskell function available in the Prelude or basic libraries.
You will find the template Haskell files in a folder on your desktop, and in VSCodium.
Please submit by dragging and dropping each Haskell file into the white box below each question. Do not rename the files before submission. You should be able to see automatic test results for your files after submission. The doctests in the file are intended to help you, but are not identical to the tests that will be used to mark you, and are not intended to be exhaustive. You may submit to the same question multiple times; if you do so, your previous submission will be overwritten.
These questions are auto-graded: you will be graded according to how many tests you pass. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam. Note that code that cannot run will receive zero marks, even if part of the code is correct. In particular, if you import packages that are not basic libraries, your code will receive zero marks.
3 i)
[6 Marks]
AnyNeg.hs
3 ii)
[6 Marks]
SafeIntDiv.hs
3 iii)
[6 Marks]
DietaryMessage.hs
3 iv)
[4 Marks]
Oblong.hs
3 v)
[4 Marks]
ReplaceSecond.hs
3 vi)
[4 Marks]
Hexadecimals.hs