All your answers will be auto-graded, so for coding problems you will be marked according to how many of our tests you pass (including example tests provided to you in the comments). Incorrect answers that pass tests will be penalised accordingly. The auto-grader will only mark code that you upload to the exam.
Writing period: 180 Minutes duration.
Study period: 15 Minutes duration (no use of keyboard).
Permitted materials: None, aside from the software environment provided.
You must attempt to answer all questions.
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
[12 Marks]
Recall the following functions from the Data.Char library:
toUpper :: Char -> Char
isUpper :: Char -> Bool
toUpper converts letters to their corresponding upper-case letters, and leaves other characters unchanged. isUpper returns True for upper-case letters, and False otherwise.
There are corresponding functions toLower and isLower for lower-case letters.
For each of the following, mark either True or False. If uncertain, use the 'clear' button to clear your answer.
True | False | ||
The type of expression (map toUpper) is [Char] -> [Char] | |||
The type of expression (filter isUpper) is [Char] -> Bool | |||
The type of expression (toUpper 'a') is [Char] | |||
The following expression is evaluated to True map toUpper ['c','A','m','E','l'] == ['C','A','M','E','L'] | |||
The following expression is evaluated to True filter isUpper ['c','A','m','E','l'] == [False] | |||
Functions (toLower . toUpper) and toUpper always produce the same outputs on the same inputs |
Question 2
[14 Marks]
Syntax
Assume a function plus :: Int -> Int -> Int has already been defined.
Some of the following expressions might be accepted by a Haskell compiler or interpreter such as ghci. Others might be accepted with warnings, or rejected. Select whether each of the expressions below are accepted or rejected by a Haskell compiler, along with the correct description accompanying the item.
2 i)
[2 Marks]
plus plus 1 2 3
Accepted because there are implicit parentheses and the compiler will be able to infer them | |
Accepted because Haskell does not need to infer the type signature of plus, since it is defined (plus :: Int -> Int -> Int) | |
Rejected because the expression is ill-typed | |
Rejected because a binary function like plus must only be written in infix notation, e.g. 1 plus 2 | |
Rejected because a binary function like plus must only be written in infix notation with parentheses, e.g. 1 (plus) 2 | |
2 ii)
[2 Marks]
plus == plus
Accepted because (==) is comparing the same functions | |
Rejected because plus returns an Int, but (==) returns a Bool | |
Rejected because Int is not a member of the Eq class | |
Rejected because Int -> Int -> Int is not a member of the Eq class | |
Rejected because Int -> Int -> Int is not a member of the Show class | |
2 iii)
[2 Marks]
c = [] ++ [plus]
Accepted and the type of c is [Int -> Int -> Int] | |
Accepted and the type of c is [[Int -> Int -> Int]] | |
Accepted and the type of c is [Int] -> [Int] -> [Int] | |
Rejected because (++) takes two lists, whereas plus takes two Ints | |
Rejected because the type of [] is [a], which is more general than the type of [plus] | |
2 iv)
[2 Marks]
z = True : False : []
Accepted and the type of z is Bool | |
Accepted and the type of z is [Bool] | |
Accepted with a warning because the empty list is unnecessary | |
Rejected because the compiler is unable to infer the type since the parentheses are missing | |
Rejected because expression (True : False) is ill-typed | |
2 v)
[2 Marks]
allTrue l = case l of
[] -> True
x:xs -> x && allTrue x
Accepted with a warning because there is no [x] case, so the pattern matches are non-exhaustive | |
Accepted with a warning because the variable x is named but not used | |
Rejected because the output is an expression of type Bool | |
Rejected because allTrue is applied to the argument of the wrong type in the recursive call | |
Rejected because the function could be written in one line using foldr | |
2 vi)
[2 Marks]
f :: (Eq a) => a -> a -> a
f a b
| a == b = b
| otherwise = a
Accepted and expression (f 3 4) is evaluated to 3 | |
Accepted and expression (f 3 4) is evaluated to 4 | |
Accepted but expression (f 3 3) would produce an error | |
Rejected because we could define it more concisely as (\x y -> x) | |
Rejected because there is a built-in Prelude function const and it is better | |
2 vii)
[2 Marks]
e = foldl (++) [] [[True],[False,True]]
Accepted and the type of e is Bool | |
Accepted and the type of e is [Bool] | |
Accepted and the type of e is [[Bool]] | |
Rejected because (++) is an operation on lists and its arguments are of type Bool here | |
Rejected because expression (foldl (++) []) must take an argument of type [Bool], but [[True],[False,True]] is of type [[Bool]]. | |
Question 3
[12 Marks]
Boolean Expressions
Using the incomplete template for BoolExpressions.hs in your exam IntelliJ project, complete the unimplemented functions (allEqual, allDifferent, exactlyTwoEqual). Use the doctests provided to test your solutions, and then upload your implementation of BoolExpressions.hs, by dragging your file into the box below.
The specifications of each function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 4
[5 Marks]
Abstraction, Algebraic Datatypes, Arithmetics
Using the incomplete template for Shapes.hs in your exam IntelliJ project, complete the unimplemented function (perimeter). Use the doctests provided to test your solution, and then upload your implementation of Shapes.hs, by dragging your file into the box below.
The specification of the perimeter function is provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 5
[7 Marks]
Enumeration Datatypes, Tuples, HOF
Using the incomplete template for Animals.hs in your exam IntelliJ project, complete the unimplemented function (animalsInContinent). Use the doctests provided to test your solutions, and then upload your implementation of Animals.hs, by dragging your file into the box below.
The specifications the animalsInContinent function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 6
[10 Marks]
Rose Trees
Using the incomplete template for Trees.hs in your exam IntelliJ project, complete the unimplemented functions (isRootElement, size, addRootValue and leaves). Use the doctests provided to test your solutions, and then upload your implementation of Trees.hs, by dragging your file into the box below.
The specifications of each function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 7
[10 Marks]
Abstraction, Lists, Function composition, Recursion
Using the incomplete template for IncreasingDifferences.hs in your exam IntelliJ project, complete the unimplemented function (increasingDifferences). Use the doctests provided to test your solutions, and then upload your implementation of IncreasingDifferences.hs, by dragging your file into the box below.
The specifications the increasingDifferences function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 8
[10 Marks]
Abstraction, Lists, HOF
Using the incomplete template for Primes.hs in your exam IntelliJ project, complete the unimplemented functions (isPrime, isEmirp, and emirps). Use the doctests provided to test your solutions, and then upload your implementation of Primes.hs, by dragging your file into the box below.
The specifications of each function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 9
[10 Marks]
Abstraction, Lists, HOF
Using the incomplete template for RLE.hs in your exam IntelliJ project, complete the unimplemented functions (encode and decode). Use the doctests provided to test your solutions, and then upload your implementation of RLE.hs, by dragging your file into the box below.
The specifications of each function are provided in the comments immediately above the function. You will need to adhere to that specification. This question is auto-graded; you will be graded according to how many tests you pass. The tests used to grade your work may differ from the ones that appear in the template file. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that nevertheless pass tests will be penalized accordingly.
Question 10
[10 Marks]
Complexity
Open the file Complexity.hs in your exam IntelliJ project. Three functions are defined: remove, smallest, and selSort. Answer the following questions about these functions' time complexity.
10 i)
[2 Marks]
What is the best case time complexity of remove?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
10 ii)
[2 Marks]
What is the average case time complexity of remove?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
10 iii)
[2 Marks]
What is the worst case time complexity of remove?
O(1) | |
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
10 iv)
[2 Marks]
What is the worst case time complexity of smallest?
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
O(n3) | |
10 v)
[2 Marks]
What is the worst case time complexity of selSort?
O(log n) | |
O(n) | |
O(n log n) | |
O(n2) | |
O(n3) | |