Total marks: 100
Reading period: 15 Minutes duration (no use of keyboard or selection of answers).
Writing period: 180 Minutes duration.
Permitted materials: One A4 page with notes on both sides, Unannotated paper-based dictionary.
Note that links to the specification of the Prelude and Data.List libraries are provided.
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
[10 Marks]
True/False questions
This question is for COMP1100 STUDENTS ONLY. Do NOT attempt if you are a COMP1130 Student.
Consider the following type declarations:
mystery :: Bool -> Int -> String -> Bool
enigma :: (String -> Bool) -> Bool
Mark True for each of the following statements if it is correct, and False if it is not.
True | False | ||
mystery True has type Int -> String -> Bool | |||
mystery . enigma is a valid composition | |||
If mystery is given only one input, the result can be used as input to enigma | |||
mystery . mystery is a valid composition | |||
The type of enigma is the same as String -> Bool -> Bool |
Question 2
[20 Marks]
Multiple choice questions
All questions in this section are for BOTH COMP1100 and COMP1130 students.
For each of the following questions, mark the single correct answer.
2 i)
[2 Marks]
Haskell variables
Which statement about variables in Haskell is false?
Their names must start with lower case letters | |
Their names should be chosen to be informative to readers of the program | |
They are used similarly to mathematics to refer to unknown values | |
They can appear between \ and -> in the syntax of anonymous functions | |
They refer to parts of the computer's memory which can be read or written to | |
2 ii)
[2 Marks]
Haskell syntax
Which of the following can be done with the Haskell keyword type?
Define a constructor that acts on types, such as Maybe | |
Define a new algebraic datatype | |
Define a synonym for a previously defined datatype | |
Output the type of the program it is applied to | |
Print to the screen or accept input from the keyboard | |
2 iii)
[2 Marks]
Lists
Which of the following statements about lists are correct?
The pattern x:y:xs represents a list with at least two elements | |
The pattern _:xs represents a list with a single element | |
The type [a] represents a list with a single element of any type | |
The type [[a]] represents a list of single element lists | |
The empty list is represented by the pattern [_] | |
2 iv)
[2 Marks]
Parametric polymorphism
Consider the following type declaration:
calculate :: a -> [a] -> b -> [(a,b)]
The first and third arguments cannot both be Int | |
It is possible for the first argument to be a Char and the second and third arguments to be String | |
If calculate were given a Double as its only input, the resulting function's first argument could have any type | |
The output of the function is a list of pairs where the two items in each pair must be different types | |
It is possible for the first argument to be an Int and the second and third arguments to be String | |
2 v)
[2 Marks]
Style
Consider the function:hasTrue :: [Bool] -> Bool
hasTrue list = case list of
[] -> False
b:bs -> b || hasTrue bs
Which of the following is the best comment for this function?
[Written next to final line] -- b is the head of the list, bs is the tail of the list | |
-- I think I could use a higher order function for this but I don't remember which one | |
-- Recurses through the input list, returning False in the base case and using || in the step case | |
-- Returns True if any Bool in the input list is True; False otherwise | |
None of these comments is adequate on their own; combining several is necessary | |
2 vi)
[2 Marks]
Folds
Which of the following pairs of functions are not mathematically equal, when we instantiate the type variables in foldl
and foldr
to both be Double
:
foldr (+) and foldl (+) | |
foldr (*) and foldl (*) | |
foldr (**) and foldl (**) | |
foldr (\_ _ -> 0) and foldl (\_ _ -> 0) | |
foldr min | |
2 vii)
[2 Marks]
Binary Search Trees
Given the standard definition of Binary Tree:
data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
Node (Node (Node Null 16 Null) 19 Null) 24 (Node (Node Null 26 Null) 28 (Node Null 31 Null))
19, 24, 26, 28, 31 | |
24, 26, 28 | |
26, 28 | |
26, 28, 31 | |
All nodes; in this worst case using a Binary Search Tree does not help | |
2 viii)
[2 Marks]
Complexity
Which of the following mathematical functions has the best (smallest) Big-O complexity?
f(x) = x2 + 1500 | |
f(x) = 2x3 + 4 | |
f(x) = 2x + 1 | |
f(x) = x * log x + 2000 | |
f(x) = x + x3 | |
2 ix)
[2 Marks]
More Complexity
Consider the following function:multiplyAll :: [Int] -> Int
multiplyAll list = case list of
[] -> 1
x:xs -> x * multiplyAll xs
What is the worst case time complexity of multiplyAll
?
O(log n) | |
O(n) | |
O(n2) | |
O(n log n) | |
O(2n) | |
2 x)
[2 Marks]
Sorting
Recall the definition of Merge Sort: merge :: Ord a => [a] -> [a] -> [a]
merge list1 list2 = case (list1,list2) of
(list,[]) -> list
([],list) -> list
(x:xs,y:ys)
| x <= y -> x : merge xs (y:ys)
| otherwise -> y : merge (x:xs) ys
mSort :: Ord a => [a] -> [a]
mSort list = case list of
[] -> []
[x] -> [x]
_ -> merge (mSort firsthalf) (mSort secondhalf)
where
firsthalf = take half list
secondhalf = drop half list
half = (length list) `div` 2
What is the worst case time complexity of mSort
?
O(n log n) | |
O(n2) | |
linear | |
exponential | |
O(n4) | |
Question 3
[5 Marks]
InLimits.hs
The following instructions apply to all programming questions below and should be read carefully.
There are seven Haskell files for COMP1100 students to complete and six Haskell files for COMP1130 students to complete. Files contain various numbers of functions to complete. Each function is worth 5 marks, except as otherwise noted in the text of HigherOrder.hs
You will find the template Haskell files in a folder on your desktop, and in VSCodium.
You may define helper functions if you wish. You may use any Haskell function available in the Prelude or basic libraries. The doctests in the file are intended to help you, but are not intended to be exhaustive, and do not replace your need to test your own code. Your code will be marked both for correctness and for other aspects of quality, such as style.
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 the text of the file you have submitted in the box. No further testing feedback will be supplied to you. You may submit to the same question multiple times; if you do so, your previous submission will be overwritten. Your work will only be visible to markers if you submit it correctly. Therefore it is essential that you upload your code into this exam by dragging your file into the appropriate box.
Complete the program InLimits.hs
in your final exam VSCodium project. This question is for COMP1100 STUDENTS ONLY. Do NOT attempt if you are a COMP1130 Student.
Question 4
[10 Marks]
Monsters.hs
Complete the program Monsters.hs
in your final exam VSCodium project. This question is for COMP1100 STUDENTS ONLY. Do NOT attempt if you are a COMP1130 Student.
Question 5
[5 Marks]
JumpAdd.hs
Complete the program JumpAdd.hs
in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.
Question 6
[15 Marks]
Maze.hs
Complete the program Maze.hs
in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.
Question 7
[10 Marks]
HigherOrder.hs
Complete the program HigherOrder.hs
in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.
Question 8
[15 Marks]
Managers.hs
Complete the program Managers.hs
in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.
Question 9
[10 Marks]
EqLists.hs
Complete the program EqLists.hs
in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.
Question 10
[5 Marks]
TypeChecking.hs
Complete the program TypeChecking.hs
in your final exam VSCodium project. This question is for COMP1130 STUDENTS ONLY. Do NOT attempt if you are a COMP1100 student.
Question 11
[20 Marks]
Lambda Calculus
All questions in this section are for COMP1130 STUDENTS ONLY. Do NOT attempt if you are a COMP1100 student.
In your answers below you may write \
for λ
and |-
for ⊢
. Write ->
to indicate that an expression beta-reduces to another, and =
for alpha-equality.
If asked to present a typing derivation, use a numbered list of typing judgements, with a clear justification beside each line, e.g.
1. x : Bool -> alpha, y : Bool |- x : Bool -> alpha [Variable]
2. x : Bool -> alpha, y : Bool |- y : Bool [Variable]
3. x : Bool -> alpha, y : Bool |- x y : alpha [1,2,Application]
4. x : Bool -> alpha |- \x. x y : Bool -> alpha [3,Lambda]
11 i)
[3 Marks]
Recall the encodings of the Boolean constants from lectures:
True
as λx.λy. x
False
as λx.λy. y
and consider the lambda term
A = λx.λy. y True (x False True)
Show using non-deterministic beta-reduction that A True False
is beta-equal to False
. Present every step of the reduction.
11 ii)
[2.5 Marks]
Present every step of the lazy evaluation of the term:
(λw.λy. w w) y ((λy.λx. y x) (x z))
11 iii)
[2.5 Marks]
Present every step of the strict evaluation of the same term:
(λw.λy. w w) y ((λy.λx. y x) (x z))
11 iv)
[4 Marks]
Suggest encodings into the untyped lambda calculus of three functions called left
, right
, and case
, obeying the following two properties:
case (left A) B C
is beta-equal to B A
case (right A) B C
is beta-equal to C A
for any lambda terms A
, B
, and C
.
You may use any the following combinators presented in lectures: True
, False
, if...then...else
, <...,...>
, fst
, snd
, all natural numbers, isZero
, succ
, pred
, and the fixed-point combinator Y
. If you use any of these combinators you should not refer to the details of their particular encodings; you may simply assume that they have been correctly encoded.
11 v)
[3 Marks]
Suppose we have two different correct encodings of the natural numbers and their operations isZero
, succ
, and pred
. To tell them apart, call the parts of one encoding
0A,1A,2A,...,isZeroA,succA,predA
and the parts of the other encoding
0B,1B,2B,...,isZeroB,succB,predB
Define a lambda term called translate
so that
translate nA
is beta-equal to nB
for any natural number n
. You may use combinators for Booleans, pairs, and the fixed-point combinator Y
, as for the previous question.
11 vi)
[5 Marks]
Give the principal type of
λx.λy.λz. x y (z y)
Justify your answer by presenting a full typing derivation.